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 (\(\forall 𝑖: 0 \le 𝑖 < 𝑛\)).

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 \(𝑛, 𝑘\) (\(𝑘 \le 𝑛 \le 10^6\))
• Dòng 2 chứa 𝑛 số nguyên dương \(𝑐_0, 𝑐_1, … , 𝑐_{𝑛−1}\) (\(\forall 𝑖: 𝑐_𝑖 \le 10^9\))

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách

Output

• 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.

Example

9 3
1 7 2 9 3 6 8 5 4

22