Cũng như mọi học sinh, Trà cố gắng đảm bảo ăn uống điều độ, đủ chất và tiết kiệm. Đã mấy năm rồi, sáng nào Trà cũng ăn hai cái bánh mỳ tròn và uống một cốc sữa đậu nành.

Sữa đậu nành đóng hộp có thể giữ khá lâu, nhưng bánh mỳ thì không để dành được quá \(k\) ngày. Giá bánh mỳ thường xuyên biến động. Nhờ tính tình vui vẻ cởi mở, Trà có quan hệ rất tốt với người bán hàng và biết được giá bánh trong \(m\) ngày tính từ hôm nay. Từ đó Trà có thể lên kế hoạch để tiết kiệm nhất trong việc mua bánh mỳ.

Ví dụ, bánh có thể giữ được trong hai ngày. Giá bánh hôm này là 3 đồng/chiếc, giá ngày mai là 1 đồng/chiếc và giá ngày kia sẽ là 2 đồng/ chiếc. Kế hoạch chi tiết kiệm của Trà sẽ là: hôm nay mua hai chiếc bánh mỳ tròn, ngày mai – sẽ mua 4 chiếc vừa ăn vừa để dành cho ngày kia. Như vậy Trà phải chi tất cả là \(3×2+1×4 = 10\).

Yêu cầu: Cho \(m, k, c_i, i =1 ÷ m\), trong đó \(c_i\) – giá một chiếc bánh mỳ tròn bán ngày thứ \(i (1 ≤ m, k, c_i ≤ 10^5)\). Hãy xác định số tiền tối thiểu cần có.

Input

• Dòng thứ nhất chứa 2 số nguyên \(m, k\),
• Dòng thứ 2 chứa \(m\) số nguyên \(c_1, c_2, ..., c_n\).

Output

• Ghi một số nguyên – chi phí tối thiểu,

Example

3 2
3 1 2 

10

2 1
1 2 

6