给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。数组的美妙之处在于该数组的某些连续子数组的最大和(该子数组可能为空)。例如数组[10,-5,10,-4,1]的美度为15,数组[-3,-5,-1]的美度为0。
您最多可以选择 $$$a$$$ 的一个连续子数组,并将该子数组中包含的所有值乘以 $$$x$$$。您希望在最多应用一次此类操作后最大限度地发挥数组的美感。
输入
第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 3 \cdot 10^5, -100 \le x \le 100$$$) — 分别是数组 $$$a$$$ 的长度和整数 $$$x$$$ 的长度。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$) — 数组 $$$a$$$。
输出
打印一个整数 — 将属于某个连续子数组 $$$x$$$ 的所有值相乘后数组 $$$a$$$ 的最大可能美丽值。
示例
输入 #1
5 -2 -3 8 -2 1 -6
输出 #1
22
输入 #2
12 -3 1 3 3 7 1 3 3 7 1 3 3 7
输出 #2
42
输入 #3
5 10 -1 -2 -3 -4 -5
输出 #3
0
注意
在第一个测试用例中,我们需要将子数组 [-2, 1, -6] 相乘,数组变为 [-3, 8, 4, -2, 12] 与美丽 22 ([-3, 8, 4, -2, 12])。
在第二个测试用例中,我们根本不需要乘以任何子数组。
在第三个测试用例中,无论我们乘哪个子数组,数组的美丽度都将等于0。