Starlight

Given an integer array and a multiplier z, you may at most once choose a contiguous segment and multiply every number in it by z; then find the maximum contiguous subarray sum of the transformed array. Skipping the amplification and taking the empty subarray are both allowed, so the answer is at least 0. The output of fixed-source example 2 is corrected from 30 to 63.

输入格式

The first line contains n z (1≤n≤200000, -100≤z≤100); the second line contains n integers (-10^9≤a[i]≤10^9).

输出格式

Output the maximum possible contiguous subarray sum.

样例 1

输入：

2 2
3 2

输出：

10

样例 2

输入：

5 -3
-5 -9 -2 1 -6

输出：

63

样例 3

输入：

4 -2
1 2 4 5

输出：

12

样例说明

Use three states to record the maximum sum of the scored segment before, inside, and after the amplified segment. In source example 2, multiplying the whole array by -3 gives 63, so the original answer 30 is wrong.