题目描述

期末到了，小慧协助班主任统计同学们本学期的德育分情况。已知学号为 $1 \sim n$ 的 $n$ 个同学的德育分，小慧有一次使用特权的机会，她可以把任意连续一段学号同学的德育分同时乘以 $C$。问小慧使用特权后，全部同学的德育分总和最多为多少分？

注意：小慧必须使用特权，不能放弃。

输入格式

第一行，两个整数 $n$ 和 $C$。 第二行，$n$ 个整数 $a_i$，按学号顺序给出 $n$ 个同学的德育分。

输出格式

输出一个整数，表示小慧能得到的最大德育分之和。

9 3
-2 1 -3 4 -1 2 1 -5 4

13

样例解释

小慧把学号 $4 \sim 7$ 的同学的分数同时乘以 $3$，数列变为 $-2, 1, -3, 12, -3, 6, 3, -5, 4$，总和为 $(-2)+1+(-3)+12+(-3)+6+3+(-5)+4 = 13$，这是能得到的最大德育分之和。

数据范围与提示

• 对于 $30\%$ 的数据：$1 \le n \le 100$，$1 \le C \le 10$，$-100 \le a_i \le 100$；
• 对于 $80\%$ 的数据：$1 \le n \le 10000$，$1 \le C \le 100$，$-1000 \le a_i \le 1000$；
• 对于 $100\%$ 的数据：$1 \le n \le 100000$，$1 \le C \le 1000$，$-10000 \le a_i \le 10000$。