BÀI 3. Ô TÔ BAY

Hãng xe ô tô VF đang thử nghiệm một loại ô tô bay. Mỗi khi gặp 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 \geq h \). Tất nhiên, "nâng" độ cao càng lớn thì năng lượng sử dụng càng nhiều, do đó VF định nghĩa "độ lãng phí" khi nâng ô tô lên chiều cao \( l \) để đi qua chướng ngại vật độ cao \( h \) là \( l - h \).
Trong thử nghiệm loại ô tô mới này, VF cho ô tô đi qua \( n \) chướng ngại vật theo thứ tự có chiều cao lần lượt là \( h_1, h_2, ..., h_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 đi 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.

Dữ liệu

Vào từ file văn bản FLYCAR.INP gồm:

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

Kết quả

Ghi ra file văn bản FLYCAR.OUT 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ý.

Ví dụ

Giải thích

Ô tô xuất phát với độ cao 7. Sau khi vượt qua chướng ngại vật thứ nhất, nó tăng độ cao lên 9, giữ nguyên độ cao này để bay qua chướng ngại vật thứ ba, thì giảm xuống độ cao 3 và bay cho đến khi vượt qua chướng ngại vật thứ sau. Tổng "độ lãng phí" là:

(7 - 7) + (9 - 9) + (9 - 8 ) + (3 - 2) + (3 - 3) + (3 - 2) = 3