A Multiply

时间限制：2s
空间限制：1024MB

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 和整数 $C$。

你可以至多进行一次以下操作：选择整数 $l,r$（$1\le l\le r\le N$），将 $A_l,A_{l+1},\ldots,A_r$ 中的每个数都乘以 $C$。

求操作后序列所有元素之和的最大值。

输入格式

第一行包含两个整数 $N,C$。

第二行包含 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示能够得到的最大元素和。

样例输入 1

5 2
-10 10 20 30 -20

样例输出 1

90

样例输入 2

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

样例输出 2

-15

样例输入 3

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

样例输出 3

13

数据范围

对于所有数据，$1\le N\le 3\times10^5$，$-10^6\le C\le10^6$，$-10^6\le A_i\le10^6$。