I. Attribute Checks
time limit per test
2.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Imagine a game where you play as a character that has two attributes: "Strength" and "Intelligence", that are at zero level initially.

During the game, you'll acquire $$$m$$$ attribute points that allow you to increase your attribute levels — one point will increase one of the attributes by one level. But sometimes, you'll encounter a so-called "Attribute Checks": if your corresponding attribute is high enough, you'll pass it; otherwise, you'll fail it.

Spending some time, you finally prepared a list which contains records of all points you got and all checks you've met. And now you're wondering: what is the maximum number of attribute checks you can pass in a single run if you'd spend points wisely?

Note that you can't change the order of records.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le m \le 5000$$$; $$$m \lt n \le 2 \cdot 10^6$$$) — the number of records in the list and the total number of points you'll get during the game.

The second line contains $$$n$$$ integers $$$r_1, r_2, \dots, r_n$$$ ($$$-m \le r_i \le m$$$), where $$$r_i$$$ encodes the $$$i$$$-th record:

  • If $$$r_i = 0$$$, then the $$$i$$$-th record is an acquiring one attribute point. You can spend to level up either Strength or Intelligence;
  • If $$$r_i \gt 0$$$, then it's an Intelligence check: if your Intelligence level is greater than or equal to $$$|r_i|$$$, you pass.
  • If $$$r_i \lt 0$$$, then it's a Strength check: if your Strength level is greater than or equal to $$$|r_i|$$$, you pass.
Output

What is the maximum number of checks you can pass if you can't change the order of records?

Examples
Input
10 5
0 1 0 2 0 -3 0 -4 0 -5
Output
3
Input
3 1
1 -1 0
Output
0
Input
9 3
0 0 1 0 2 -3 -2 -2 1
Output
4