D. Проверка характеристик
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте себе игру, в которой вы играете за персонажа с двумя характеристиками: «Сила» и «Интеллект», которые изначально находятся на нулевом уровне.

В ходе игры вы получите $$$m$$$ очков характеристик, которые позволят вам поднять их уровни — одно очко увеличивает одну из характеристик на один уровень. Но в процессе игры вы также сталкиваетесь с так называемыми «Проверками характеристик»: если ваша соответствующая характеристика достаточно высока, вы пройдете проверку; в противном случае вы провалите проверку.

Потратив некоторое время, вы наконец подготовили список, который содержит записи обо всех очках, которые вы получили, и всех проверках, с которыми столкнулись. И теперь вы задаетесь вопросом: каково максимальное количество проверок характеристик, которые вы можете пройти за одну игру, если будете разумно тратить очки?

Обратите внимание, что вы не можете изменить порядок записей.

Входные данные

В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le 5000$$$; $$$m < n \le 2 \cdot 10^6$$$) — количество записей в списке и общее количество очков, которые вы получите в ходе игры.

Во второй строке заданы $$$n$$$ целых чисел $$$r_1, r_2, \dots, r_n$$$ ($$$-m \le r_i \le m$$$), где $$$r_i$$$ кодирует $$$i$$$-ю запись:

  • Если $$$r_i = 0$$$, то $$$i$$$-я запись является записью о получении одного очка характеристик. Вы можете потратить его на повышение уровня либо Силы, либо Интеллекта;
  • Если $$$r_i > 0$$$, то это проверка Интеллекта: если ваш уровень Интеллекта больше или равен $$$|r_i|$$$, вы проходите проверку.
  • Если $$$r_i < 0$$$, то это проверка Силы: если ваш уровень Силы больше или равен $$$|r_i|$$$, вы проходите проверку.

Дополнительное ограничение на входные данные: в заданной последовательности $$$r_1, r_2, \dots, r_n$$$ ровно $$$m$$$ элементов, равных $$$0$$$.

Выходные данные

Выведите одно целое число — максимальное количество проверок, которые вы можете пройти.

Примеры
Входные данные
10 5
0 1 0 2 0 -3 0 -4 0 -5
Выходные данные
3
Входные данные
3 1
1 -1 0
Выходные данные
0
Входные данные
9 3
0 0 1 0 2 -3 -2 -2 1
Выходные данные
4
Примечание

В первом тесте оптимально вложить каждое очко в Силу, поэтому вы провалите $$$2$$$ проверки Интеллекта, но пройдете $$$3$$$ проверки Силы.

Во втором тесте вы провалите обе проверки, так как первое очко характеристик приходит только после проверок.

В третьем тесте одной из оптимальных стратегий является:

  1. вложить первое очко в Интеллект;
  2. вложить второе очко в Силу;
  3. вложить третье очко в Силу;
В результате вы пройдете $$$2$$$ проверки Интеллекта $$$r_3$$$ и $$$r_9$$$ и $$$2$$$ проверки Силы $$$r_7$$$ и $$$r_8$$$.