Đào hiện tại đang có một dãy ~a~ có ~n~ phần tử và một số nguyên ~x~. Hiện tại Đào đang muốn thực hiện thao tác sau nhiều nhất một lần: nhân một đoạn con của chính dãy này với ~x~.

Yêu cầu: Biết rằng một đoạn con là một dãy các phần tử liên tiếp nhau trong một dãy số, hãy tính xem tổng đoạn con lớn nhất là bao nhiêu sau khi Đào thực hiện thao tác nhiều nhất một lần.

Input

Dòng đầu tiên gồm hai số nguyên ~n~ và ~x~ (~n ≤ 10^5, |x| ≤ 1000~) — lần lượt là độ dài của dãy ~a~ và số ~x~.

Dòng thứ hai gồm một dãy nguyên ~a_1,a_2,...,a_n (1 ≤ |a_i| ≤ 1000)~ — giá trị thứ ~i~ của dãy ~a~

Output

Gồm một số nguyên duy nhất là tổng đoạn con lớn nhất tìm được.

Scoring

Sample Input 1

5 2
-1 2 -1 3 -3

Sample Output 1

8

Sample Input 2

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

Sample Output 2

-1

Notes

• Ở ví dụ thứ nhất, nhân đoạn con bắt đầu từ vị trí ~1~ đến ~4~, dãy số mới ta nhận được là ~[-2, 4, -2, 6, -3]~. Tổng đoạn con lớn nhất tìm được là ~[4, -2, 6] = 8~ với vị trí bắt đầu từ ~2~ cho đến ~4~.
• Ở ví dụ thứ hai, Đào chọn không nhân ~x~ với bất kì đoạn con nào. Khi đó, tổng đoạn con lớn nhất tìm được là ~[-1]~ có tổng là ~-1~.