Tập chạy

Khánh muốn tăng cường sức khỏe nên anh ấy tham gia tập chạy. Mỗi ngày Khánh chạy chính xác n phút, tại mỗi phút bất kì, có thể lựa chọn chạy hay nghỉ ngơi trong phút đó. Khi bắt đầu chạy độ mệt mỏi của Khánh là 0. Tại phút t bất kì, nếu chọn phương án là chạy thì Khánh chạy được chính xác d_t mét và độ mệt mỏi sẽ tăng lên 1 đơn vị, tuy nhiên độ mệt mỏi không được tăng quá M; nếu chọn nghỉ ngơi thì độ mệt mỏi giảm đi 1 đơn vị, độ mệt mỏi không thể giảm quá 0 (độ mệt mỏi đang là 0 mà chọn nghỉ ngơi thì sau khi nghỉ ngơi độ mệt mỏi vẫn là 0). Khánh chỉ có thể bắt đầu chạy trở lại khi không mệt mỏi. Sau khi kết thúc n phút chạy Khánh cũng phải cảm thấy không mệt mỏi thì mới tăng cường được sức khỏe.

Yêu cầu: Hãy tìm khoảng cách lớn nhất mà Khánh có thể chạy.

Dữ liệu: Vào từ file văn bản TAPCHAY.INP gồm 2 dòng:

• Dòng đầu chưa 2 số nguyên dương  n và M (1 ≤ n ≤10⁴, 1≤M ≤  500)
• Dòng tiếp theo chứa n số nguyên dương, số thứ  t là d_t (1≤d_t ≤ 1000).

Kết quả: Ghi ra file văn bản TAPCHAY.OUT: một số là khoảng cách lớn nhất mà Khánh có thể chạy được.

Ví dụ

Giải thích: phút 1 chạy (được 5 mét) độ mệt mỏi là 1,phút 2 nghỉ ngơi, phút 3 chạy (được 4 mét), nghỉ ngơi phút 4 và 5, tổng quãng đường chạy được là  9 mét.

Rằng buộc:

• Có ½ các test có N ≤  10³
• Có 1/3 các test còn lại có 10³ <  N  ≤  10⁴