Hãng xe ô tô BT đang thử nghiệm môt loai ô tô bay. Mỗi khi găp một chướng ngai vật có độ cao \(h\), ô tô có thể đi qua chướng ngại vật này bằng cách "nâng" độ cao của mình cách mặt đất môt khoảng \(l \ge h\). Tất nhiên "nâng" độ cao càng lớn thì nhiên liệu sử dụng càng nhiều. Do đó BT định nghĩa "độ lãng phí" khi nâng ô tô lên chiều cao \(l\) để đi qua chướng ngại vật chiều cao \(h\) là \(l-h\).

Trong ngày thử nghiệm loại ô tô mới này, BT cho ô tô đi qua n chướng ngại vật theo thứ tự có chiều cao là \(h_1,h_2,…,h_n\). Tất nhiên khi đi qua chướng ngại vât nào ô tô phải duy trì chiều cao tối thiểu bằng chướng ngại vật đó. Do đang là phiên bản thử nghiệm nên trong suốt quá trình đia qua n chướng ngại vật ô tô chỉ có thể thay đổi độ cao không quá \(k\) lần.

Yêu cầu: Viết chương trình lên lịch thay đổi độ cao của ô tô sao cho tổng "độ lãng phí" khi đi qua n chướng ngại vật là nhỏ nhất? Ô tô có thể khởi hành với độ cao ban đầu bất kỳ và việc xuất phát đưa ô tô lên độ cao ban đầu này không được tính vào \(k\) lần thay đổi độ cao.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n,k\) (\(1\le k<n\le 400\))
• Dòng thứ hai chứa n số nguyên \(h_1,h_2,…,h_n\) (\(0\le h_i\le 10^9\)) là độ cao của các chướng ngại vật lần lượt xuất hiện trên hành trình.

Output

• In ra một số nguyên là "tổng độ lãng phí" nhỏ nhất khi thay đổi độ cao của ô tô một cách hợp lý.

Example

6 2
7 9 8 2 3 2

3