F - Laminat胶板

得分：600分

问题陈述

我们将在一个白色的正方形网格中，涂黑一些方格，该网格有$10^9$行和$N$列。
当前计划如下：对于从左边开始的第$i$列，我们将涂黑最下面的$H_i$个方块，而不涂黑该列中的其他方块。
在开始工作之前，您可以选择最多$K$列（可能为零），并更改这些列的$H_i$值，取值范围为$0$到$10^9$（包括$0$和$10^9$）。
可以为不同的列选择不同的值。

然后，您将通过重复执行以下操作来创建修改后的艺术品：

• 在一行中选择一个或多个连续的方格并将其涂黑。(已经涂黑的方格可以再次涂黑，但根据修改后的方案不需要涂黑的方格则不应涂黑）

找到需要执行此操作的最小次数。

约束

• $1 \leq N \leq 300$
• $0 \leq K \leq N$
• $0 \leq H_i \leq 10^9$
• 输入中的所有值都为整数。

输入

输入以如下格式从标准输入中给出：

$N$ $K$

$H_1$ $H_2$ $...$ $H_N$

4 1
2 3 4 1

3

例如，通过将$H_3$的值更改为$2$，您可以通过以下三个操作创建修改后的艺术品：

• 将位于底部第$1$行的从左到右的$1$到$4$个方块涂黑。
• 将位于底部第$2$行的从左到右的$1$到$3$个方块涂黑。
• 将位于底部第$3$行的从左到右的第$2$个方块涂黑。

6 2
8 6 9 1 2 1

7

比如改成 3 6 3 1 2 1

10 0
1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000

4999999996