题目描述

题目描述

我们将在一个白色的正方形网格中，涂黑一些方格，该网格有$10^9$行和N列。

当前计划如下:对于从左边开始的第列，我们将涂黑最下面的$H_i$个方块，而不涂黑该列中的其他方块。

在开始工作之前，您可以选择最多$K$列(可能为零)，并更改这些列的$H_i$值，取值范围为0到$10^9$(包括0和$10^9$)。

可以为不同的列选择不同的值。

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

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

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

输入

第一行两个整数$N,K$

第二行一共$N$个整数，表示$H_i$

输出

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

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

提示

• $1\ \leq\ N\ \leq\ 300$
• $0\ \leq\ K\ \leq\ N$
• $1\ \leq\ H_i\ \leq\ 10^9$