Bắn tàu là trò chơi khá phổ biến và có nhiều phiên bản. Hãy cùng xét một phiên bản của trò chơi này. Có ~N~ tàu của địch đang hoạt động ngoài khơi được đánh số từ ~1~ đến ~N~, tàu thứ ~i~ luôn cách bờ một khoảng ~d_i~.

Nhiệm vụ của người chơi là phải phá hủy hết các tàu theo thứ tự tàu ~1~, tàu ~2~, ... đến tàu ~N~. Người chơi được cung cấp vũ khí là một loại ngư lôi, ban đầu có thể được thiết lập ở bất kỳ mức năng lượng nào và trong quá trình chơi được thay đổi qua một mức năng lượng bất kỳ tối đa ~K~ lần ~(1 \leq K < N)~.

Nếu được thiết lập ở mức năng lượng ~R~ thì khi bắn ngư lôi có thể phá hủy một tàu cách bờ trong phạm vi nhỏ hơn hay bằng ~R~ đơn vị chiều dài. Ở lần bắn tàu thứ ~i~, nếu khoảng cách ~d_i~ nhỏ hơn mức năng lượng hiện tại ~R~ của ngư lôi thì người chơi bị trừ một số điểm là ~R - d_i~ (vì sử dụng lãng phí năng lượng).

Viết chương trình cho biết số điểm bị trừ ít nhất sau khi người chơi phá hủy hết ~N~ tàu.

Input

Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ cho biết số lượng tàu và số lần tối đa đổi mức năng lượng của ngư lôi.

Dòng thứ 2 chứa ~N~ số nguyên, số thứ ~i~ cho biết ~d_i~ ~(0 \leq d_i \leq 10^6)~ là khoảng cách tới bờ của tàu thứ ~i~.

Output

Một số nguyên duy nhất là số điểm bị trừ ít nhất sau khi người chơi phá hủy hết ~N~ tàu.

Sample Input 1

7 1
80 10 5 7 100 20 35

Sample Output 1

313

Sample Input 2

7 2
80 10 5 7 100 20 35

Sample Output 2

153

Scoring

Notes

Test 1:

Ban đầu ngư lôi có mức năng lượng là 100.

Sau lần bắn thứ 5, thay đổi năng lượng về mức 35.

Test 2:

Ban đầu ngư lôi có mức năng lượng là 80.

Sau lần bắn thứ 1, thay đổi năng lượng về mức 10.

Sau lần bắn thứ 4, thay đôi năng lượng về mức 100.