{"code":"flying_car","name":"Ô tô bay","description":"### Ô tô bay\r\nHã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$.\r\n\r\nTrong 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.\r\n\r\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.\r\n\r\n#### Input\r\nDòng đầu chứa hai số nguyên dương $n,k$ ($1 \\le k < n \\le 400$).\r\nDò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.\r\n\r\n#### Output\r\nIn 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ý.\r\n\r\n\r\n!!! question \"Test 1\"\r\n???+ \"Input\"\r\n    ```\r\n    6 2\r\n    7 9 8 2 3 2\r\n    ```\r\n??? success \"Output\"\r\n    ```\r\n    3\r\n    ```\r\n??? warning \"Note\"\r\n    Ví dụ: khởi hành ở độ cao $7$. Sau chướng ngại vật thứ nhất tăng lên $9$, giữ nguyên đến sau chướng ngại vật thứ ba thì hạ xuống $3$ và giữ đến hết. Tổng ``độ lãng phí``:\r\n    $$\r\n    (7-7)+(9-9)+(3-2)+(3-3)+(3-2)=3.\r\n    $$","points":100.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}