Anh T có một vườn mận sắp đến mùa thu hoạch. Tuy nhiên, anh T đang gặp vấn đề trong việc thu hoạch. Các cây mận trong vườn chín không đều mà chín trải dài trong $n$ ngày. Theo tính toán của anh T thì tại ngày thứ $i$ sẽ có $a[i]$ cây mận chín. Cây mận chín trong ngày thứ $i$ thì chỉ có thể thu hoạch trong ngày thứ $i$ và ngày thứ $i$+1 mà thôi, nếu thu hoạch chậm hơn thì mận sẽ bị hỏng. Hiện tại do thiếu phương tiện nên năng suất thu hoạch trong 1 ngày chỉ được $m$ cây mận thôi. Bạn hãy giúp anh T lập kế hoạch sao cho thu hoạch được nhiều cây mận nhất nhé.

Input

Dòng thứ nhất gồm hai số $n$, $m$ cách nhau một khoảng trắng (1 <= $n$, $m$ <=${10}^5$)

Dòng thứ hai gồm $n$ số $a[1]$, $a[2]$, ..., $a[n]$, mỗi số cách nhau một khoảng trắng (1 <= $a[i]$ <= ${10}^5$)

Output

Một dòng duy nhất là số cây mận nhiều nhất anh T có thể thu hoạch được

Ví dụ

Input

4 2
1 2 3 4

Output

9

Giải thích Ngày thứ nhất thu hoạch 1 cây, các ngày 2, 3, 4 mỗi ngày thu hoạch 2 cây. Ngày thứ 5 thu hoạch thêm 2 cây chín trong ngày 4. Tổng cộng 9 cây.