После второго прибытия на Пандору «небесных людей» и создания ими новой базы Джейк Салли стал часто совершать нападения на поезда, транспортирующие ресурсы и оружие. Поскольку вооружение людей сильно превосходит вооружение На'ви, к каждому рейду приходится подходить очень ответственно.
В очередной рейд могут отправиться $$$n$$$ представителей племени Оматикайя, $$$i$$$-й из которых обладает силой $$$a_i$$$ и скоростью своего икрана $$$b_i$$$.
Чтобы рейд удался, Джейк собирается выбрать команду из нескольких (одного или больше) представителей племени и выстроить их в последовательность $$$i_1, i_2, \ldots, i_k$$$ так, чтобы
Джейк хочет взять в рейд как можно больше На'ви, при этом соблюдая описанные условия. Племя Оматикайя большое, поэтому он может найти и позвать еще одного участника рейда помимо описанных $$$n$$$ с произвольными параметрами силы и скорости.
Помогите Джейку определить, На'ви с какими параметрами $$$a$$$ и $$$b$$$ ему следует позвать в рейд, чтобы в рейд могло отправиться как можно больше участников.
В первой строке через пробел даны два целых числа $$$n$$$ и $$$x$$$ — количество желающих принять участие в рейде и параметр разрешенной разницы в скорости ($$$1 \leqslant n \leqslant 2 \cdot 10^5$$$; $$$0 \leqslant x \leqslant 10^9$$$).
В следующих $$$n$$$ строках через пробел записаны по два целых числа $$$a_i$$$ и $$$b_i$$$ — параметры силы и скорости участников рейда ($$$1 \leqslant a_i, b_i \leqslant 10^9$$$).
Выведите длину самого длинного возможного строя участников рейда и пару параметров дополнительного участника $$$(a, b)$$$, добавлением которого можно ее достичь. Параметры $$$a$$$ и $$$b$$$ должны лежать от $$$1$$$ до $$$10^9$$$ включительно.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 12 | $$$n \leqslant 10$$$ | полная | |
2 | 13 | $$$x = 0$$$; $$$a_i = b_i$$$ для всех $$$i$$$ | первая ошибка | |
3 | 17 | $$$x = 0$$$ | 2 | первая ошибка |
4 | 17 | все $$$a_i$$$ равны | первая ошибка | |
5 | 19 | $$$n \leqslant 1000$$$ | 1 | первая ошибка |
6 | 22 | нет | 1 — 5 | первая ошибка |
1 5 3 3
2 3 3
3 3 1 2 2 5 4 11
4 2 8