Hưng muốn tăng cường sức khỏe nên anh ấy tham gia tập chạy. Mỗi ngày anh ta chạy chính xác ~N~ phút, tại ~1~ phút bất kỳ, anh ta có thể lựa chọn là chạy hay nghỉ ngơi trong phút đó.

Khi bắt đầu chạy, độ mệt mỏi của anh ta là ~0~. Tại phút thứ ~i~ bất kỳ, nếu anh ta chọn phương án là chạy thì anh ấy chạy được chính xác ~D_i~ mét và độ mệt mỏi sẽ tăng lên ~1~, tuy nhiên độ mệt mỏi không được tăng quá ~M~, nếu anh ta chọn nghỉ ngơi thì độ mệt mỏi giảm đi ~1~ đơn vị, và anh ta không thể bắt đầu chạy trở lại cho đến khi độ mệt mỏi trở về ~0~.

Sau khi kết thúc ~N~ phút chạy, độ mệt mỏi của anh ấy cũng phải trở về ~0~ (nếu không anh ta sẽ không thể làm việc cả ngày hôm đó).

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

Input

• Dòng 1: ~N~ và ~M~ (~1 \le N \le 10.000~; ~1 \le M \le 500~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi ~D_i~ (~1 \le D_i \le 1.000~).

Output

• Một số duy nhất là khoảng cách xa nhất.

Sample Input 1

5 2
5
3
4
2
10

Sample Output 1

9