Các con bò muốn giỏi thể thao hơn, nên Bessie tập trên đường chạy đúng $N$ $(1 \le N \le 10,000)$ phút. Mỗi phút chọn chạy hoặc nghỉ suốt phút đó.

Tổng quãng đường phụ thuộc “hệ số mệt mỏi”, ban đầu bằng 0. Chạy trong phút $i$ đi đúng $D_i$ $(1 \le D_i \le 1,000)$ và tăng hệ số 1, nhưng không bao giờ vượt $M$ $(1 \le M \le 500)$. Nghỉ giảm 1 mỗi phút. Không thể chạy lại cho đến khi hệ số đạt 0; lúc ấy có thể chạy hoặc nghỉ.

Kết thúc $N$ phút, hệ số của Bessie phải đúng 0, nếu không thiếu năng lượng cho phần còn lại trong ngày.

Tìm quãng đường chạy lớn nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

• Dòng 1: số nguyên $N$ và $M$ cách nhau dấu cách.
• Dòng $2..N+1$: dòng $i+1$ chứa duy nhất số nguyên $D_i$.

Dữ liệu ra

Ghi ra đầu ra chuẩn.

• Dòng 1: một số nguyên là quãng đường lớn nhất thỏa các điều kiện.

Ví dụ

Dữ liệu vào 1

5 2
5
3
4
2
10

Dữ liệu ra 1

9

Ghi chú

Bessie chạy phút đầu ($distance=5$), nghỉ phút hai, chạy phút ba ($distance=4$), nghỉ phút bốn và năm. Không thể chạy phút năm vì hệ số cuối không bằng 0.

Tác giả: Neal Wu, 2007