题目描述

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

输入格式

第一行，两个整数 $n$ 和 $c$ ；

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

输出格式

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

样例

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$，得到最大德育分数之和为 $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$。