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