Một công ty vận tải quản lý tuyến đường cao tốc gồm ~n~ đoạn liên tiếp, trong đó đoạn đường thứ ~i~ mang lại giá trị lợi nhuận là ~a_i~ (có thể âm do chi phí vận hành). Công ty muốn lựa chọn một đoạn liên tiếp bất kỳ trên tuyến đường sao cho tổng lợi nhuận thu được là lớn nhất. Nếu không tồn tại đoạn nào có tổng lợi nhuận dương thì lợi nhuận tối đa được tính bằng ~0~.

Ngoài ra, công ty có thể sử dụng tối đa một lần nâng cấp đặc biệt lên một đoạn liên tiếp ~[u, v]~ ~(1 \le u \le v \le n)~. Khi áp dụng nâng cấp, toàn bộ các đoạn đường từ ~u~ đến ~v~ sẽ có lợi nhuận mới là ~a_i \times x~, với ~x~ là một số nguyên cho trước. Công ty có thể chọn sử dụng hoặc không sử dụng nâng cấp này.

Yêu cầu: Tính giá trị lợi nhuận lớn nhất có thể của một đoạn con liên tiếp khi áp dụng hoặc không áp dụng nâng cấp đặc biệt.

Input

• Dòng ~1~: Hai số nguyên ~n~, ~x~ ~(1 \le n \le 5 \times 10^5; -10^6 \le x \le 10^6)~;

• Dòng ~2~: ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(-10^6 \le a_i \le 10^6)~.

Output

Một số nguyên duy nhất là giá trị lợi nhuận lớn nhất có thể.

Scoring

Sample Input 1

5 -3
-1 2 4 -3 4

Sample Output 1

19