题目描述

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

输入描述

第一行，两个整数 n 和 c； 第二行，n 个整数，按学号顺序给出 n 个同学的德育分 a i ​ 。

输出描述

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

用例输入 1

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

用例输出 1

13

提示

样例解释：

小慧把 4 ~ 7号同学的分数同时乘以 3，变为 −2, 1, −3, 12, −3, 6, 3, −5, 4，得到最大德育分数之和为 13。

数据范围：

对于 30% 的数据，1<=n<=100，1<=c<=10，−100<=ai<=100；

对于 80% 的数据，1<=n<=10000，1<=c<=100，−1000<=ai<=1000；

对于 100% 的数据，1<=n<=100000，1<=c<=1000，−10000<=ai<=10000。