最大值

题目描述

给定一个长度为 (N) 的整数序列 A=(\(A_1,A_2,\dots,A_N\)) 和一个整数 (C)。 你可以至多进行一次如下操作：选择一对整数 (l,r) 满足 (\(1\le l\le r\le N\))，将区间 (\(A_l,A_{l+1},\dots,A_r\)) 的所有元素乘以 (C)。

请你求出通过至多一次该操作后，序列 (A) 全体元素之和能够达到的最大值。

约束

• 输入均为整数
• (\(1 \le N \le 3\times 10^5\))
• (\(-10^6 \le C \le 10^6\))
• (\(-10^6 \le A_i \le 10^6\))

输入

从标准输入按以下格式给出：

N C
A1 A2 … AN

输出

输出一个整数，表示可达到的最大总和。

样例 1

输入

5 2
-10 10 20 30 -20

输出

90

说明：此时 A=(-10,10,20,30,-20), C=2。选择 (l=2, r=4) 进行一次操作，可得新序列 (-10,20,40,60,-20)，其元素和为 90，为可达到的最大值。

样例 2

输入

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

输出

-15

说明：若不进行任何操作，元素和为 (-15)，这已是最大值。

样例 3

输入

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

输出

13