题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$ 和一个整数 $C$。
请你求出通过至多一次如下操作后，$A$ 的所有元素之和的最大值。

• 选择满足 $1\le l\le r\le N$ 的整数 $l,r$，将 $A_l,A_{l+1},\dots,A_r$ 的所有元素都乘以 $C$。

输入格式

输入以以下格式从标准输入读入。

$N$ $C$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请输出一个整数，表示最大可能的 $A$ 的所有元素之和。

样例 1

输入

5 2
-10 10 20 30 -20

输出

90

样例 2

输入

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

输出

-15

样例 3

输入

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

输出

13

说明/提示

限制条件

• 所有输入均为整数。
• $1\le N\le 3\times 10^5$
• $-10^6\le C\le 10^6$
• $-10^6\le A_i\le 10^6$

样例解释 1

本样例中，$A=(-10,10,20,30,-20),\ C=2$。选择 $l=2, r=4$ 并进行一次操作后，$A$ 变为 $(-10,20,40,60,-20)$。此时 $A$ 的所有元素之和为 $90$，这是可以达到的最大值。

样例解释 2

本样例中，$A=(-1,-2,-3,-4,-5),\ C=1000000$。如果不进行任何操作，$A$ 的所有元素之和为 $-15$，这是可以达到的最大值。

由 ChatGPT 4.1 翻译