Anh Bo có một vườn táo sắp đến mùa thu hoạch. Tuy nhiên các cây táo 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 Bo thì tại ngày thứ i sẽ có a_i cây táo chín. Cây táo 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ì táo bị hỏng. Hiện tại do thiếu phương tiện nên năng suất thu hoạch trong 01 ngày chỉ được m cây mà thôi. Bạn hãy giúp anh Bo lập kế hoạch sao cho thu hoạch được nhiều cây nhất nhé.

Dữ liệu nhập:

- Dòng thứ nhất gồm hai số n, m cách nhau một khoảng trắng (1 ≤ n, m ≤ 1.000) 

- Dòng thứ hai gồm n số a₁, a₂, ..., a_n, mỗi số cách nhau một khoảng trắng (0 ≤ a_i ≤ 1.000)

Dữ liệu xuất:

- Số lượng cây táo nhiều nhất mà anh Bo có thể thu hoạch.

Example

Input

4 2
1 2 3 4

Output

9