You are an accountant at a YC-backed AI startup, and you are yet to make substantial profit despite millions in investment. However, you need more money to fund the endless cycle of new products, so your CEO has instructed you to cook the books a little to make your finances more presentable to investors. You have a ledger of ~n~ days of earning reports, and you may delete up to ~k~ listings before people notice your cooking.

Within these parameters, you have to make your finances as appealing to investors as possible. This measure of "appeal" is defined as follows: the investors are busy and have short attention spans, so they will always read the earnings in string chronological order from ~1~ to ~n~. Moreover, they always want to see green: if the cumulative sum of earnings goes into the negative at any point, they'll stop reading and have their verdict. So, your appeal value is some integer ~L~ such that all the prefix sums among the first ~L~ days, that is ~a_1~, ~a_1+a_2~, ~\ldots~, ~a_1+\ldots+a_L~, are all nonnegative. Can you cook the books, or is your company cooked?

Input

The first line consists of two integers ~n~ ~(1 \leq n \leq 5\times 10^5)~ and ~k~ ~(0 \leq k \leq n)~, where ~n~ represents the number of days worth of ledger entries you have, and ~k~ represents the maximum number of entries you can delete.

The next line contains ~n~ space-separated integers ~a_1\ a_2\ \ldots\ a_n~ ~(-10^9 \leq a_i \leq 10^9)~, the earnings report on each day.

Output

Output the largest integer ~L~ such that none of the first ~L~ prefix sums are negative that can be obtained by removing up to ~k~ entries. That is,

$$\displaystyle \forall l \in [1,L],\, \sum_{i=1}^l A_i \geq 0$$

The indices referenced are in the new array after removing elements, so they will not count the removed entries.

Example

Input 1

6 1
5 -4 -3 2 -5 1

Output 1

3

The sum of the first three elements is negative, so we must remove either ~-4~ or ~-3~. Then, we can take the entry with ~2~, but either way the ~-5~ will send us into the negatives, and we have already necessarily used our ~1~ removal. Thus, since ~2~ is the fourth element of the input array and we have removed one, there are ~3~ days in our presentable period.

Input 2

7 3
-4 -3 -2 -1 5 1000000 -3

Output 2

0

The first four elements are all negative, and we can only remove three at maximum, so there is no way we can make any presentable prefix. Thus, our output is ~0~.

Input 3

8 3
1 2 -4 2 -1 5 -10 8

Output 3

6

It is possible to remove ~2~ elements such that the entire remaining book is presentable. We must remove both ~-4~ and ~-10~. The prefix sum will become ~0~ at ~-1~, but presentability is only defined as a nonnegative prefix sum, so this is fine. Thus, we output ~6~ as the input was ~8~ and we have removed ~2~.