题目描述

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

输入格式

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

输出格式

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

样例输入

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

样例输出

13

提示

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

数据范围：

• 对于30%的数据，1≤n≤100，1≤c≤10，-100≤a_i≤100；
• 对于80%的数据，1≤n≤10000，1≤c≤100，-1000≤a_i≤1000；
• 对于100%的数据，1≤n≤100000，1≤c≤1000，-10000≤a_i≤10000。