Cho một dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1,a_2,…,a_n~. Gọi ~f(A)~ là giá trị của dãy con liên tiếp có tổng lớn nhất của dãy ~A~. Ví dụ: ~A=(5,-1,2,-3) → f(A)=5+(-1)+2=6~.

Yêu cầu: Cho một số nguyên ~x~, hãy tìm cách tăng mỗi phần tử trong tối đa một dãy con liên tiếp của dãy ~A~ lên ~x~ lần sao cho ~f(A)~ lớn nhất có thể.

**Dữ liệu vào: **

• Dòng đầu tiên chứa số hai số nguyên ~n~ và ~x~ ~(n ≥ 1, |x| ≤ 100)~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…,a_n~ ~(|a_i | ≤ 100);~

Kết quả:

• In ra kết quả bài toán là giá trị lớn nhất của ~f(A)~.

Ví dụ:

Input:

5 2
5 -1 2 -3 2 

Output:

12 

Giải thích:

Ta nhân ~a_1~ với ~x~, tức là ~a_1 = a_1 × 2 = 5 × 2 = 10~. Sau đó thì ~A=(10,-2,4,-3,2)→f(A)=10+(-2)+4=12~.

Giới hạn:

• ~30~%: ~n ≤ 50~
• ~30~%: ~n ≤ 2000~
• ~40~%: ~n ≤ 3.10^5~