Cho dãy ~A = (a_1, a_2, ..., a_n)~. Độ đẹp của dãy ~A~ được định nghĩa là tổng lớn nhất của một đoạn con liên tiếp (có thể rỗng) của dãy. Chẳng hạn, dãy ~A = (-3, 8, 4, -2, 12)~ có độ đẹp bằng ~22~ (đoạn con ~(8, 4, -2, 12)~), dãy ~B = (-1, -2, -3, -4, -5)~ có độ đẹp bằng ~0~ (đoạn con rỗng).

Yêu cầu

Để gia tăng độ đẹp của dãy ~A~, bạn được phép chọn tối đa một đoạn con liên tiếp của dãy và nhân từng phần tử trong đoạn con đó lên ~X~ lần. Xác định độ đẹp lớn nhất có thể đạt được của dãy.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng 1: hai số nguyên ~N, X~ ~(1 \le N \le 4 \times 10^5;\ -100 \le X \le 100)~;
• Dòng 2: ~N~ số nguyên ~a_1, a_2, ..., a_N~ ~(|a_i| \le 10^9)~.

Dữ liệu đầu ra

Gồm một số nguyên là độ đẹp tối đa của dãy ~A~ sau khi thực hiện không quá một thao tác nói trên.

Ràng buộc dữ liệu

• 20% điểm dành cho các test có ~1 \le N \le 50~;
• 30% điểm khác dành cho các test có ~1 \le N \le 300~;
• 20% điểm khác dành cho các test có: ~a_i \ge 0 \ \forall\ i~;
• 30% điểm còn lại không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

INPUT

5 -2
-3 8 -2 1 -6

OUTPUT

22

Giải thích: Thực hiện thao tác với đoạn ~[-2, 1, -6]~ thu được dãy ~[-3, 8, \underline{4, -2, 12}]~. Dãy này có độ đẹp là ~22~, đây là độ đẹp lớn nhất có thể đạt được.

Ví dụ 2

INPUT

8 -4
1 2 1 1 2 0 0 7

OUTPUT

14

Giải thích: Không cần thực hiện thao tác nào.

Ví dụ 3

INPUT

5 10
-1 -2 -3 -4 -5

OUTPUT

0