Giáo sư X dự định thực hiện một chuyến đi bằng ô tô trên con đường dài ~n~ km tính từ km ~0~ (nơi xuất phát) tới km ~n~ (nơi kết thúc). Ô tô của giáo sư ~X~ có bình xăng dung tích là ~k~ lít, mỗi lít xăng cho phép ô tô đi được quãng đường dài đúng ~1~ km.
Tại mỗi mốc km, từ mốc km ~0~ tới mốc km ~n − 1~, có một trạm xăng, tại đó giáo sư X có thể mua thêm xăng nạp vào bình, tuy nhiên bình xăng không thể chứa quá ~k~ lít tính cả lượng xăng còn lại trong xe trước khi mua. Giá xăng ở trạm xăng tại mốc km thứ ~i~ là ~c_i~ một lít (~∀i: 0 ≤ i < n~).
Hãy tìm cách thực hiện chuyến đi với tổng số tiền mua xăng thấp nhất. Biết rằng giáo sư X xuất phát từ km số ~0~ với một bình xăng rỗng.
Dữ liệu:
- Dòng 1 chứa hai số nguyên dương ~n, k\ (k ≤ n ≤ 10^6~)
- Dòng 2 chứa ~n~ số nguyên dương ~c_0, c_1, … , c_{n−1}\ (∀i: c_i ≤ 10^9~)
Các số trên một dòng được ghi cách nhau bởi dấu cách
Kết quả: Ghi ra một số nguyên duy nhất là tổng số tiền mua xăng theo phương án tìm được.
Ví dụ:
INPUT
9 3
1 7 2 9 3 6 8 5 4
OUTPUT
22
![](http://oj.lequydon.net/media/martor/5aa3b51a-0226-4d32-bad5-7f9570b65620.png)
Comments