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.