Кеши устраивает вечеринку и хочет, чтобы все на ней были счастливы.
У него есть \(n\) друзей. У его \(i\)-го друга есть \(i\) долларов.
Если пригласить \(i\)-го друга на вечеринку, то он будет счастлив только в том случае, если не более \(a_i\) человек на вечеринке будут строго богаче его и не более \(b_i\) человек будут строго беднее его.
Кеши хочет пригласить как можно больше людей. Найдите максимальное число людей, которых он может пригласить на вечеринку, чтобы каждый приглашенный был счастлив.
Выходные данные
Для каждого набора входных данных выведите максимальное количество людей, которых может пригласить Кеши.
Примечание
В первом наборе входных данных он приглашает первого и второго человека. Если он пригласит всех, то третий человек не будет счастлив, потому что будет более чем \(1\) человек беднее его.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
1 2
2 1
1 1
2
0 0
0 1
2
1 0
0 1
|
2
1
2
|