题目描述

给定一个整数序列 $a_1,\dots,a_n$ ，小爱需要通过一系列调整操作将所有数字改成 $0$。

在调整开始前，他有$m$次机会，每次机会可以将序列中任意一个整数更改成他想要的值。然后，在每步调整操作中，他可以选择一段连续的区间（也可以只选一个数），将所选的全部数字减少一单位。

请问小爱最少需要几步调整操作才能将所有数字改成 $0$？

输入

输入共两行：第一行，两个正整数$n,m$

第二行，$n$个正整数$a_1,a_2,...,a_n$

$1 \leq n \leq 300$，$0 \leq m \leq n$，$1 \leq a_i \leq 10^9$

输出

输出共一行，一个正整数，表示最少需要的操作次数

样例

4 2
3 1 2 4

2

提示

开始调整前，先利用2次机会，将序列改成{1，1，2，2}

第一次选择[1，4]区间操作，将区间内数字-1，得{0，0，1，1}

第二次选择[3，4]区间操作，将区间内数字-1，得{0，0，0，0}

将所有数字改成 0 共需两次操作。

1s, 512MB 每组测试数据