Ô tô bay

Hãng xe ô tô Hoàng đang thử nghiệm một loại ô tô bay. Mỗi khi gặp một chướng ngại 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 đó Hoàng định nghĩa độ lãng phí khi nâng ở độ lên chiều cao \(l\) để đi qua chướng ngại vật cao \(h\) là \(l-h\).

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

Yêu cầu: Lên lịch thay đổi độ cao để 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 đưa ô tô lên độ cao ban đầu này không tính vào \(k\) lần thay đổi.

Input

Dòng đầu 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,\dots,h_n\) (\(0 \le h_i \le 10^9\)), là độ cao các chướng ngại vật theo thứ tự xuất hiện.

Output

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

6 2
7 9 8 2 3 2

3