Mô tả và yêu cầu

Hãy 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 ℎ, ô 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 𝑙 ≥ ℎ. 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
𝑙 để đi qua chướng ngại vật độ cao ℎ là 𝑙 − ℎ.
Trong thử nghiệm loại ô tô mới này, VF cho ô tô đi qua 𝑛 chướng ngại vật theo thứ
tự có chiều cao lần lượt là ℎ1, ℎ2, … ,ℎ𝑛. 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á 𝑘 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 𝑛 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 𝑘
lần thay đổi độ cao.
Dữ liệu: vào từ thiết bị nhập chuẩn gồm
 Dòng đầu tiền chứa 2 số nguyên dương 𝑛, 𝑘(1 ≤ 𝑘 < 𝑛 ≤ 400).
 Dòng thứ hai chứa 𝑛 số nguyên dương ℎ1, ℎ2, … ,ℎ𝑛(0 ≤ ℎ𝑖 ≤ 109) 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 thiết bị xuất chuẩn chứa 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ụ

INPUT                                          OUTPUT
 6 2                                              3
 7 9 8 2 3 2

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