Vào sinh nhật thứ 11 của mình, Harry Potter được mời đến trường phù thủy để học. Một trong những bài học đầu tiên là sử dụng cây đũa thần. Harry ra vườn hoa của trường để tập luyện.

Trường Hogwarts có một luống hoa dài trồng ~N~ cây hoa phép thuật, cây thứ ~i~ có vẻ đẹp là ~a[i]~. Chọn ra một đoạn gồm các cây hoa liền tiếp có tổng lớn nhất chính là vẻ đẹp của luống hoa. Nếu không có đoạn nào có tổng dương, thì vẻ đẹp của luống hoa được tính là ~0~.

Harry có thể không sử dụng đũa thần hoặc sử dụng đũa thần một lần duy nhất để làm phép thuật lên luống hoa. Phép thuật có thể tác động lên một đoạn bất kỳ gồm các cây hoa liền tiếp. Gọi ~[u..v]~ là đoạn mà Harry đã làm phép (~1 ≤ u ≤ v ≤ N~). Khi đó, cây hoa thứ ~i~ (với ~u ≤ i ≤ v~) sẽ có giá trị vẻ đẹp mới là ~a[i] * X~.

Harry muốn làm phép thuật sao cho vẻ đẹp của luống hoa là lớn nhất có thể. Tuy nhiên luống hoa khá dài và Harry chưa biết chọn đoạn nào để làm phép. Hãy giúp Harry!

Yêu cầu: Cho ~N, X, a~, hãy giúp Harry tính vẻ đẹp tối đa của luống hoa sau khi sử dụng phép thuật.

Input

Vào từ file văn bản FLOWER.INP:

• Dòng thứ nhất: hai số nguyên ~N, X~ (~1 \leq N \leq 5*10^5, -10^6 \leq X \leq 10^6~);
• Dòng thứ hai: ~N~ số nguyên ~a[1],a[2],...,a[N]~ (~-10^6 \leq a[i] \leq 10^6~).
-

Output

Vào từ file văn bản FLOWER.OUT một số nguyên duy nhất — vẻ đẹp tối đa của luống hoa sau khi Harry sử dụng phép thuật.

Scoring

• Subtask ~1~ ~(40\%)~: ~1 \leq N \leq 50~;
• Subtask ~2~ ~(20\%)~: ~50 < N \leq 500~;
• Subtask ~3~ ~(20\%)~: ~500 < N \leq 5000~.
• Subtask ~4~ ~(20\%)~: ~5000 < N \leq 5*10^5~.

Example input 1

5 2
-1 2 4 -3 4

Example output 1

14

Note 1

• Làm phép đoạn ~[2,4,-3,4]~ luống hoa trở thành: ~[-1, 4, 8, -6, 8]~ có vẻ đẹp là ~4+8-6+8 = 14~.

Example input 2

5 -3
-1 2 4 -3 4

Example output 2

19

Note 2

• Làm phép đoạn ~[-3]~ luống hoa trở thành: ~[-1, 2, 4, 9, 4]~ có vẻ đẹp là ~2+4+9+4 = 19~.

Example input 3

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

Example output 3

0

Note 3

• Có làm phép thuật hay không thì vẻ đẹp vẫn là ~0~.