Bản dịch tiếng việt

Đề được dịch lại từ tiếng trung và đảm bảo đề có nghĩa 99%

Cho ~N~ trạm máy chủ xếp thành một hàng ngang từ ~1~ đến ~N~. Mỗi trạm ~i~ có một độ ưu tiên tải là ~A_i~ (có thể nhận giá trị âm, bằng ~0~, hoặc dương).

Bạn cần chọn ra một tập hợp gồm ~K~ khoảng máy chủ không chồng lấp nhau ~(0 \le K \le N)~ để kích hoạt. Khoảng thứ ~j~ kéo dài từ vị trí ~L_j~ đến ~R_j~ thỏa mãn:

~1 \le L_1 \le R_1 < L_2 \le R_2 < \dots < L_K \le R_K \le N~

Mỗi khoảng được chọn bắt buộc phải có độ dài chẵn (tức là ~R_j - L_j + 1~ chia hết cho ~2~).

Tổng lợi nhuận thu được khi kích hoạt ~K~ khoảng bằng tổng giá trị tải của các máy chủ thuộc các khoảng được chọn trừ đi chi phí kích hoạt ~K \times P~ (với ~P~ là chi phí phạt cố định cho mỗi khoảng):

$$\text{Profit} = \left(\sum_{j=1}^{K} \sum_{i=L_j}^{R_j} A_i\right) - K \times P$$

Hãy tính lợi nhuận ròng lớn nhất có thể đạt được.

Input

• Dòng thứ ~1~ chứa ~2~ số nguyên ~N~ và ~P~ ~(1 \le N \le 500000, 0 \le P \le 10^{14})~, cách nhau bởi ~1~ dấu cách.
• Dòng thứ ~2~ chứa ~N~ số nguyên ~A_1, A_2, \dots, A_N~ ~(-10^9 \le A_i \le 10^9)~, các số cách nhau bởi ~1~ dấu cách.

Output

Ghi ra ~1~ số nguyên duy nhất là lợi nhuận ròng lớn nhất tìm được.

Sample Input

6 2
3 -1 4 2 -5 6

Sample Output

7

Subtask

• ~15~% số test tương ứng với ~15%~ số điểm có ~N \le 200~ và ~P \le 1000~
• ~25%~% số test tiếp theo tương ứng với ~25%~ số điểm có ~N \le 2000~
• ~20%~% số test tiếp theo tương ứng với ~20%~ số điểm có ~N \le 100000~ và ~P = 0~
• ~40%~% số test còn lại tương ứng với ~40%~ số điểm không có điều kiện gì thêm

Note

Giải thích ví dụ mẫu: Ta chọn ~K = 2~ khoảng:

• Khoảng ~1~: Từ ~1~ đến ~4~ ~(L_1 = 1, R_1 = 4)~ có độ dài ~4~ (chẵn), tổng giá trị là ~3 + (-1) + 4 + 2 = 8~.
• Khoảng ~2~: Từ ~5~ đến ~6~ ~(L_2 = 5, R_2 = 6)~ có độ dài ~2~ (chẵn), tổng giá trị là ~-5 + 6 = 1~.

Tổng lợi nhuận thu được là ~(8 + 1) - 2 \times 2 = 5~.

Tuy nhiên, phương án tối ưu hơn là chỉ chọn ~K = 1~ khoảng duy nhất từ ~1~ đến ~6~ ~(L_1 = 1, R_1 = 6)~ với độ dài ~6~ (chẵn):

• Tổng giá trị: ~3 + (-1) + 4 + 2 + (-5) + 6 = 9~.
• Chi phí kích hoạt: ~1 \times 2 = 2~.
• Lợi nhuận ròng lớn nhất: ~9 - 2 = 7~.

Bản gốc (tiếng trung)