Vào sinh nhật thứ 11, Harry Potter tập luyện phép cây đũa thần trên một luống hoa gồm ~N~ cây, mỗi cây có vẻ đẹp ~a[i]~ (có thể âm). Vẻ đẹp của luống hoa được định nghĩa là tổng lớn nhất của một đoạn liên tiếp (maximum subarray sum). Nếu không có đoạn nào có tổng > 0, vẻ đẹp được tính là 0.

Harry có thể không dùng hoặc dùng đúng một lần phép thuật trên một đoạn liên tiếp ~[u..v]~: sau phép, mọi cây trong đoạn đó đều được nhân ~\times X~, tức ~a[i] := a[i]\cdot X~ với ~u \le i \le v~. Hãy giúp Harry đạt vẻ đẹp tối đa cho luống hoa.

Yêu cầu

Cho ~N~, ~X~, và dãy ~a~, hãy tính vẻ đẹp tối đa của luống hoa sau khi Harry có thể thực hiện tối đa một phép nhân đoạn bởi ~X~ (hoặc không làm gì).

Dữ liệu

• Dòng 1: hai số nguyên ~N, X~ (~-10^6 \le X \le 10^6~).
• Dòng 2: ~N~ số nguyên ~a[1], a[2], \ldots, a[N]~ (~-10^6 \le a[i] \le 10^6~).

Kết quả

In ra một số nguyên duy nhất là vẻ đẹp tối đa của luống hoa sau khi sử dụng phép thuật.

Ví dụ

Ví dụ 1

Input

5 2
-1 2 4 -3 4

Output

14

Ví dụ 2

Input

5 -3
-1 2 4 -3 4

Output

19

Ví dụ 3

Input

5 3
-1 -2 -3 -5 -2

Output

0

Giải thích

• Ví dụ 1: Làm phép trên đoạn ~[2..5]~ biến dãy thành ~[-1, 4, 8, -6, 8]~; đoạn có tổng lớn nhất có giá trị ~14~.
• Ví dụ 2: Làm phép trên đoạn ~[-3]~ được dãy ~[-1,2,4,9,4]~, tổng lớn nhất ~2+4+9+4=19~.
• Ví dụ 3: Dù có nhân đoạn nào thì tổng lớn nhất vẫn không dương, nên đáp án là ~0~.

Chấm điểm

• 40% số điểm: ~1 \le N \le 50~.
• 20% số điểm: ~50 < N \le 500~.
• 20% số điểm: ~500 < N \le 5000~.
• 20% số điểm: ~5000 < N \le 50000~.

$$ \text{Gợi ý: dùng } \\ \max\_{\text{đoạn}} \left(\underbrace{\text{prefix-best}}\_{\text{trước}},~\underbrace{\text{best với nhân }X}\_{\text{giữa}},~\underbrace{\text{suffix-best}}\_{\text{sau}}\right) \text{ hoặc quy hoạch động/kadane mở rộng với ba trạng thái.} $$