Представьте себе игру, в которой вы играете за персонажа с двумя характеристиками: «Сила» и «Интеллект», которые изначально находятся на нулевом уровне.
В ходе игры вы получите \(m\) очков характеристик, которые позволят вам поднять их уровни — одно очко увеличивает одну из характеристик на один уровень. Но в процессе игры вы также сталкиваетесь с так называемыми «Проверками характеристик»: если ваша соответствующая характеристика достаточно высока, вы пройдете проверку; в противном случае вы провалите проверку.
Потратив некоторое время, вы наконец подготовили список, который содержит записи обо всех очках, которые вы получили, и всех проверках, с которыми столкнулись. И теперь вы задаетесь вопросом: каково максимальное количество проверок характеристик, которые вы можете пройти за одну игру, если будете разумно тратить очки?
Обратите внимание, что вы не можете изменить порядок записей.
Выходные данные
Выведите одно целое число — максимальное количество проверок, которые вы можете пройти.
Примечание
В первом тесте оптимально вложить каждое очко в Силу, поэтому вы провалите \(2\) проверки Интеллекта, но пройдете \(3\) проверки Силы.
Во втором тесте вы провалите обе проверки, так как первое очко характеристик приходит только после проверок.
В третьем тесте одной из оптимальных стратегий является:
- вложить первое очко в Интеллект;
- вложить второе очко в Силу;
- вложить третье очко в Силу;
В результате вы пройдете
\(2\) проверки Интеллекта
\(r_3\) и
\(r_9\) и
\(2\) проверки Силы
\(r_7\) и
\(r_8\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 5
0 1 0 2 0 -3 0 -4 0 -5
|
3
|
|
2
|
3 1
1 -1 0
|
0
|
|
3
|
9 3
0 0 1 0 2 -3 -2 -2 1
|
4
|