У Беси есть \(N\) (\(1\le N\le 2\cdot 10^5\)) работ для Вас. Если Вы выберете
\(i\)-ую работу, её необходимо начать в момент времени \(s_i\) или до него и для
её завершения требуется \(t_i\) единиц времени.
(\(0\le s_i\le 10^{18}, 1\le t_i\le 10^{18}\)).
Какое максимальное количество работ Вы успеете выполнить?
Время начинается с \(0\),и, если Вы начали работу, Вы сначала должны
выполнить и только потом начинать другую работу.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(T\), количество независимых подтестов (
\(1\le T\le 10\)).
Каждый подтест представлен следующим образом:
Первая строка содержит число \(N\).
Каждая из последующих \(N\) строк содержит два целых числа \(s_i\) и \(t_i\).
Строка \(i+1\) содержит описание \(i\)-ой работы.
Гарантируется, что сумма \(N\) по всем подтестам не превысит
\(3\cdot 10^5\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Для каждого подтеста в отдельной строке выведите максимальное количество работ
которое Вы сможете выполнить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2
1 4
1 2
2
2 3
1 2
3
1 4
2 3
1 2
|
1
2
2
|