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 đúng N phút (vừa chạy vừa nghỉ), 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 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ếu độ mệt mỏi bằng không thì anh ta có nghỉ cũng không giảm nữa), và anh ta không thể bắt đầu chạy 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 đó). Hãy tìm độ dài quãng đường lớn nhất mà Hưng có thể chạy trong một ngày?

Dữ liệu vào:

Dòng đầu tiên chứa hai số nguyên dương N và M.(1≤N≤100000; 1≤M≤500);

Dòng tiếp theo chứa N số nguyên d[1],d[2],…,d[N].

Dữ liệu ra:

Một số nguyên duy nhất là độ dài quãng đường lớn nhất mà Hưng có thể chạy trong một ngày.

Dữ liệu vào:

5 2
5 3 4 2 10

Dữ liệu ra:

`` 9

## Giải thích:

Phút 1: Chạy 5m Phút 2: Nghỉ Phút 3: Chạy 4m Phút 4, 5: Nghỉ ```