Một cửa hàng có ~N~ món hàng được bày bán trên quầy theo thứ tự từ trái sang phải, đánh số từ ~1~ đến ~N~. Món hàng thứ ~i~ có giá tiền là ~A_i~.

Nhân một dịp đặc biệt, chủ cửa hàng quyết định thực hiện chính sách giảm giá. Cụ thể với món hàng thứ ~i~, gọi ~B~ là mảng giá tiền của các món hàng còn trên quầy nằm bên trái ~i~ có giá tiền rẻ hơn ~A_i~, sau khi sắp xếp ~B~ tăng dần, nếu số lượng phần tử của ~B~ không nhỏ hơn ~K~ thì có thể mua món hàng ~i~ với giá ~B_K~. Ngược lại, nếu số lượng phần tử của ~B~ nhỏ hơn ~K~ thì món hàng ~i~ sẽ vẫn giữ giá cũ. Một món hàng khi được bán thì sẽ được đem đi khỏi quầy.

Anh là một người đam mê mua sắm. Anh muốn mua hết tất cả các món hàng. Thật may mắn là ngoài Anh ra không có ai mua cả, nên Anh có thể tự do chọn mua món hàng nào trước mà không sợ món hàng bị mua mất. Tuy nhiên, Anh vẫn là người chi tiêu hợp lý, anh muốn mua hết tất cả món hàng với số tiền bỏ ra là ít nhất.

Hãy tính số tiền nhỏ nhất mà Anh bỏ ra để mua hết tất cả món hàng.

Dữ liệu

• Dòng đầu chứa 2 số nguyên dương ~N~ và ~K~ ~(1 \le N \le 3000,\ 1 \le K \le N)~.

• Dòng thứ 2 chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^9)~ là giá tiền của các món hàng.

Kết quả

In ra số tiền nhỏ nhất mà Anh phải trả để mua hết tất cả các món hàng.

Ví dụ

Sample Input

5 2
1 3 2 4 3

Sample Output

10

Giải thích

Anh chọn mua các món hàng theo vị trí lần lượt là ~5, 4, 3, 2, 1~ với giá tiền mua từng món hàng lần lượt là ~2, 2, 2, 3, 1~. Tổng giá tiền Anh phải trả là ~10~.