Background

Special for beginners, ^_^

Description

有 $n（\le300）$ 根柱子，每根柱子的高度不超过 $10^9$ 。

每次作弊，可以选中一根柱子把高度修改为任意非负整数值。

最多可以作弊 $k$ 次。

每次操作，可以选中一排连续的柱子，把它们的高度减1。[L, R]就像俄罗斯方块那样消掉一层。

在至多修改 $k$ 次柱子高度的前提下，让所有柱子消失至少需要多少次操作。

Format

Input

第一行两个整数 $n$ 和 $k$ ，分别表示柱子的数量和修改的次数上限（当然不会超过 $n$ ）。

接下来一行给出 $n$ 个数，表示从左到右每根柱子的高度。

Output

输出最多作弊 $k$ 次的前提下，完成消消乐的最少次数。

Samples

6 2
7 5 8 1 2 1

6

Limitation

1s, 1024KiB for each test case.