Score: $300$ points

问题陈述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$，以及一个整数 $C$。 在执行以下操作 最多一次 后，找出 $A$ 中元素的最大可能和：

• 指定整数 $l$ 和 $r$，使得 $1 \le l \le r \le N$，并将 $A_l,A_{l+1},\dots,A_r$ 每个元素乘以 $C$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given an integer sequence of length $N$, $A=(A_1,A_2,\dots,A_N)$, and an integer $C$.
Find the maximum possible sum of the elements in $A$ after performing the following operation at most once:

• Specify integers $l$ and $r$ such that $1 \le l \le r \le N$, and multiply each of $A_l,A_{l+1},\dots,A_r$ by $C$.

Constraints

• All input values are integers.
• $1 \le N \le 3 \times 10^5$
• $-10^6 \le C \le 10^6$
• $-10^6 \le A_i \le 10^6$

Input

The input is given from Standard Input in the following format:

$N$ $C$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answer as an integer.

Sample Input 1

5 2
-10 10 20 30 -20

Sample Output 1

90

In this input, $A=(-10,10,20,30,-20), C=2$.
After performing the operation once specifying $l=2$ and $r=4$, $A$ will be $(-10,20,40,60,-20)$.
Here, the sum of the elements in $A$ is $90$, which is the maximum value achievable.

Sample Input 2

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

Sample Output 2

-15

In this input, $A=(-1,-2,-3,-4,-5), C=1000000$.
Without performing the operation, the sum of the elements in $A$ is $-15$, which is the maximum value achievable.

Sample Input 3

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

Sample Output 3

13