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 ~A~. 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).

Để 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 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.

Yêu cầu: Hãy xác định độ đẹ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.

Input

• Dòng 1: hai số nguyên dương ~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~).

Output

Dòng 1: 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.

Sample Input 1

5 -2
-3 8 -2 1 -6

Sample Output 1

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, 4, -2, 12]~. Dãy này có độ đẹp là 22.

Sample Input 2

8 -4
1 2 1 1 2 0 0 7

Sample Output 2

14

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

Sample Input 3

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

Sample Output 3

0

Subtasks

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