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, giả sử 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 số 0 tới mốc km số 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 thứ i là c_i một lít (0 ≤ i < n).

Hãy tìm cách giúp giáo sư X 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à bắt đầu đổ xăng, trước đó bình xăng rỗng.

Dữ liệu vào: Đọc từ tệp Cau5.inp:

- Dòng 1 chứa hai số nguyên dương n, k (k ≤ n ≤ 1000).

- Dòng 2 chứa n số nguyên dương c₀, c₁, …, c_n-1 (với: c_i ≤ 10⁹).

Kết quả ra: Ghi dữ liệu ra tệp Cau5.out một số nguyên duy nhất là tổng số tiền mua xăng theo phương án tối ưu.

Ví dụ:

Cau5.inp

9 3
1 7 2 9 3 6 8 5 4

Cau5.out

22