Паркування кораблів#3131
Життя на великих океанах було добрим для капітана Чорної Бороди та його товаришів-піратів. Вони зібрали стільки скарбів, що кожен з них може купити будинок на своєму улюбленому острові. Будинки на цьому острові розташовані в довгий ряд вздовж берегової лінії. Крім будинку, кожен пірат також може купити собі корабель для грабунків. Проте, це породжує нову проблему.
Вздовж берегової лінії є довгий пірс, де кожен пірат може припаркувати свій корабель. Хоча на пірсі достатньо місця для всіх кораблів, не кожен пірат зможе припаркуватися навпроти свого будинку. Пірат задоволений своїм паркувальним місцем, якщо якась частина паркувального місця знаходиться навпроти центру його будинку. Капітану Чорній Бороді випала важка задача — призначити місця для паркування піратам. Паркувальне місце для пірата — це відрізок [a_i, b_i] (a_i, b_i \in \mathbb{R}) уздовж пірсу такий, що l_i \leq b_i - a_i, де l_i — довжина корабля пірата . Таким чином, пірат буде задоволений, якщо a_i \leq x_i \leq b_i, де x_i — центр будинку пірата . Зрозуміло, паркувальні місця різних піратів повинні бути внутрішньо неперетинними (краї відрізків можуть збігатися).
Над усе капітан хоче добре паркувальне місце для себе, тому резервує паркувальне місце так, щоб центр його корабля був вирівняний із центром його будинку. Він також хоче зробити щасливими якомога більше піратів. Чи зможете ви йому допомогти?
Перший рядок містить одне ціле число: кількість тестів. Кожен тест має такий формат:
Один рядок із одним цілим числом (1 \leq n \leq 1\,000): кількість піратів разом із капітаном.
рядків, кожен з яких містить два цілі числа x_i (-10^9 \leq x_i \leq 10^9) і l_i (1 \leq l_i \leq 10^9): центр будинку -го пірата та повна довжина його корабля відповідно. Перший пірат у вхідних даних завжди є капітаном. Гарантується, що всі x_i різні.
Для кожного тесту виведіть одне ціле число в окремому рядку: максимальну кількість щасливих піратів за оптимального розподілу паркувальних місць. Це число включає капітана. Можна вважати, що місця на пірсі необмежені в обидві сторони.
Приклад 1