题目描述

We will create an artwork by painting black some squares in a white square grid with $10^9$ rows and $N$ columns.
The current plan is as follows: for the $i$-th column from the left, we will paint the $H_i$ bottommost squares and will not paint the other squares in that column.
Before starting to work, you can choose at most $K$ columns (possibly zero) and change the values of $H_i$ for these columns to any integers of your choice between $0$ and $10^9$ (inclusive).
Different values can be chosen for different columns.

Then, you will create the modified artwork by repeating the following operation:

• Choose one or more consecutive squares in one row and paint them black. (Squares already painted black can be painted again, but squares not to be painted according to the modified plan should not be painted.)

Find the minimum number of times you need to perform this operation.

我们将在一个行数为 $10^9$ 列数为 $N$ 的白色方格中涂黑一些方格，从而创作一幅作品。
目前的计划如下：对于从左边开始的 $i$ （第 1 列），我们将涂上最下面的 $H_i$ 个方格，而不涂画该列中的其他方格。
在开始工作之前，你可以选择最多 $K$ 列（可能为零），并将这些列的 $H_i$ 值改为 $0$ 和 $10^9$ （含）之间的任意整数。
不同的列可以选择不同的值。

然后，重复以下操作，创建修改后的作品：

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

请计算执行此操作的最少次数。

输入格式

输入内容按以下格式标准输入：

$N$ $K$
$H_1$ $H_2$ $...$ $H_N$

输出格式

打印所需的最少操作数。

样例 #1

样例输入 #1

4 1
2 3 4 1

样例输出 #1

3

样例 #2

样例输入 #2

6 2
8 6 9 1 2 1

样例输出 #2

7

样例 #3

样例输入 #3

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

样例输出 #3

4999999996

说明

数据规模与约定

• $1 \leq N \leq 300$
• $0 \leq K \leq N$
• $0 \leq H_i \leq 10^9$
• 输入值均为整数。

样例 $1$ 解释

例如，将 $H_3$ 的值更改为 $2$ ，就可以通过以下三种操作创建修改后的图样：

• 涂黑第 $2$ 行从下往左起的第 $1$ 到第 $3$ 个方格。
• 把从下往上第 $3$ 行中左边的第 $2$ 个方格涂成黑色。