Giáo sư X dự định thực hiện một chuyến đi bằng ô tô trên con đường dài 𝑛 km tính từ km 0 (nơi xuất phát) tới km 𝑛 (nơi kết thúc). Ô tô của giáo sư X có bình xăng dung tích là 𝑘 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 𝑛 − 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á 𝑘 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ứ 𝑖 là 𝑐𝑖 một lít (∀𝑖: 0 ≤ 𝑖 < 𝑛).

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ừ 𝑘𝑚 số 0 với một bình xăng rỗng.

Input:

• Dòng 1 chứa hai số nguyên dương 𝑛, 𝑘 (𝑘 ≤ 𝑛 ≤ 10^6)

• Dòng 2 chứa 𝑛 số nguyên dương 𝑐0, 𝑐1, … , 𝑐[𝑛−1] (∀𝑖: 𝑐𝑖 ≤ 10^9)

Output:

Một số nguyên duy nhất là tổng số tiền mua xăng theo phương án tìm được.

Sample Input

9 3 
1 7 2 9 3 6 8 5 4

Sample Output

22