Maximum Profit Window

A trading desk may apply one boost to its daily results: choose at most one contiguous segment of days and multiply every value in it by X. (Choosing no segment is allowed.)

Find the maximum possible total sum of the array after the boost.

Input

The first line contains two integers n and X.

The second line contains n integers a₁ … aₙ.

Output

Print the maximum possible total.

Constraints

• 1 ≤ n ≤ 2·10⁴
• −10⁷ ≤ aᵢ ≤ 10⁷
• 1 ≤ X ≤ 10⁵
• The answer can be far outside 32-bit range — use 64-bit integers.

5 3
1 -2 4 -1 3

17

3 5
-1 -2 -3

-6