Description

長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ と整数 $C$ が与えられます。 以下の操作を 高々 $1$ 度 行って達成できる $A$ の全要素の総和の最大値を求めてください。

• $1\ \le\ l\ \le\ r\ \le\ N$ を満たす整数 $l,r$ を指定し、 $A_l,A_{l+1},\dots,A_r$ の全ての要素を $C$ 倍する。

翻译：

给出 $N, C, A_{1 \dots n}$。你可以选择一个区间 $[l, r]$，让 $A_l, A_{l+1}, \dots, A_r$ 全部乘上 $C$。至多一次操作后，求 $A_{1 \dots n}$ 的和的最大值。

Format

Input

第一行两个整数 $N$ 和 $C$

第二行$N$个整数 $A_1, A_2, \dots, A_N$

Output

输出一个整数表示答案

Samples

输入输出样例 #1

输入 #1

5 2
-10 10 20 30 -20

输出 #1

90

输入输出样例 #2

输入 #2

5 1000000
-1 -2 -3 -4 -5

输出 #2

-15

输入输出样例 #3

输入 #3

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

输出 #3

13

Limitation

说明/提示

制約

• 入力は全て整数
• $1\ \le\ N\ \le\ 3\ \times\ 10^5$
• $-10^6\ \le\ C\ \le\ 10^6$
• $-10^6\ \le\ A_i\ \le\ 10^6$

Sample Explanation 1

この入力では、 $A=(-10,10,20,30,-20),\ C=2$ です。 $l=2,r=4$ と指定して操作を $1$ 度行うことで、操作後の $A$ を $(-10,20,40,60,-20)$ とすることができます。 このとき $A$ の全要素の総和は $90$ となり、これが達成可能な最大値です。

Sample Explanation 2

この入力では、 $A=(-1,-2,-3,-4,-5),\ C=1000000$ です。 操作を一度も行わないとき $A$ の全要素の総和は $-15$ となり、これが達成可能な最大値です。