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.