Description

While walking along the edge of his farmland, Uncle Fang suddenly noticed that one row of corn looked very unattractive. There are $N$ stalks in this row, and their heights vary. Uncle Fang thinks a non-decreasing sequence is beautiful, so he decides to first raise some stalks and then pull out any stalks that spoil the beauty, so that the heights of the remaining stalks form a non-decreasing sequence. He may choose an interval and increase every stalk in that interval by 1 unit of height; he may perform at most $K$ such operations. He may also freely choose any set of stalks to remove. What is the maximum number of stalks that can remain to form a beautiful row?

Input Format

The first line contains two integers $n$, $K$, denoting the number of stalks in this row and the maximum number of operations allowed, respectively. The second line contains $n$ integers; the $i$-th number is the height $a_i$ of the $i$-th stalk from left to right.

Output Format

Output a single integer, the maximum number of remaining stalks.

3 1
2 1 3

3

Hint

Constraints: $100\%$ of the testdata satisfies: $2 \le N \lt 10^4$, $2 \le K \le 500$, $1 \leq a_i \leq 5000$.

Translated by ChatGPT 5