Рейд на транспортер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

После второго прибытия на Пандору «небесных людей» и создания ими новой базы Джейк Салли стал часто совершать нападения на поезда, транспортирующие ресурсы и оружие. Поскольку вооружение людей сильно превосходит вооружение На'ви, к каждому рейду приходится подходить очень ответственно.

В очередной рейд могут отправиться $$$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$$$ включительно.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112$$$n \leqslant 10$$$полная
213$$$x = 0$$$; $$$a_i = b_i$$$ для всех $$$i$$$первая ошибка
317$$$x = 0$$$2первая ошибка
417все $$$a_i$$$ равныпервая ошибка
519$$$n \leqslant 1000$$$1первая ошибка
622нет1 — 5первая ошибка

Примеры

Входные данные
1 5
3 3
Выходные данные
2 3 3
Входные данные
3 3
1 2
2 5
4 11
Выходные данные
4 2 8