题目描述

我们将通过在白色方格网格中涂黑一些方块来创建一幅艺术作品，该网格有$10^9$行和$N$列。

当前的计划如下：对于从左边起的第$i$列，我们将涂黑最底部的$H_i$个方块，并且不会涂黑该列的其他方块。

在开始工作之前，你可以选择至多$K$个列（可能为零），并将这些列的$H_i$的值更改为你选择的任意整数，取值范围为$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$

输出

打印需要的最小操作次数。

示例输入 1

4 1
2 3 4 1

示例输出 1

3

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

• 从底部开始，涂黑第一行中从左边起的第一个到第四个方块。
• 从底部开始，涂黑第二行中从左边起的第一个到第三个方块。
• 从底部开始，涂黑第三行中从左边起的第二个方块。

示例输入 2

6 2
8 6 9 1 2 1

示例输出 2

7

示例输入 3

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

示例输出 3

4999999996