Кеши устраивает вечеринку и хочет, чтобы все на ней были счастливы.
У него есть $$$n$$$ друзей. У его $$$i$$$-го друга есть $$$i$$$ долларов.
Если пригласить $$$i$$$-го друга на вечеринку, то он будет счастлив только в том случае, если не более $$$a_i$$$ человек на вечеринке будут строго богаче его и не более $$$b_i$$$ человек будут строго беднее его.
Кеши хочет пригласить как можно больше людей. Найдите максимальное число людей, которых он может пригласить на вечеринку, чтобы каждый приглашенный был счастлив.
Первая строка содержит одно целое число $$$t$$$ $$$(1\le t\le 10^4)$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ $$$(1\le n\le 2 \cdot 10^5)$$$ — количество друзей Кеши.
$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ $$$(0 \le a_i, b_i < n)$$$.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите максимальное количество людей, которых может пригласить Кеши.
3 3 1 2 2 1 1 1 2 0 0 0 1 2 1 0 0 1
2 1 2
В первом наборе входных данных он приглашает первого и второго человека. Если он пригласит всех, то третий человек не будет счастлив, потому что будет более чем $$$1$$$ человек беднее его.
| Codeforces Global Round 17 |
|---|
| Закончено |
