ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Весна — 2023» > задача:


F. Макс и аттракционы

Отборочный турнир сезона «Весна — 2023»

Старт: 06.мая.2023 в 10:00:00
Финиш: 14.мая.2023 в 23:00:00
Турнир завершён!
• Турнирная таблица

Гость
• Вопросы к жюри (1)

Задачи турнира

• A. Макс и термометр
• B. Макс и ключ
• C. Макс и ДНК
• D. Макс и объединение результатов
• E. Макс и дни рождения великих
• F. Макс и аттракционы
• G. Макс и математические часы
• H. Макс и формирование букета
• I. Макс и номера телефонов
• J. Макс и кубик Рубика 2x2x2

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и аттракционы
Макс и аттракционы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Макс пришёл в парк развлечений. Всего в парке есть $$$N$$$ аттракционов, у $$$i$$$-го из которых стоимость билета составляет $$$A_i$$$ рублей, а удовольствие от посещения равно $$$B_i$$$.

Макс мог бы посещать аттракционы в любом порядке, однако он считает, что в процессе посещения парка нельзя понижать планку, поэтому каждый следующий посещённый им аттракцион должен стоить строго больше и приносить строго больше удовольствия, чем предыдущий. В качестве первого Макс всё ещё может выбрать любой аттракцион.

Помогите Максу узнать, какое наибольшее количество аттракционов он сможет посетить в парке.

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — количество аттракционов в парке.

Следующие $$$N$$$ строк описывают аттракционы. Каждая из них содержит целые числа $$$A_i$$$ и $$$B_i$$$ ($$$1 \le A_i, B_i \le 10^9$$$) — соответственно цену билета и удовольствие от посещения $$$i$$$-го аттракциона.

Выходные данные

Выведите одно целое число — наибольшее возможное количество аттракционов, которые Макс сможет посетить.

Примеры

Входные данные
5
1 5
5 1
2 2
3 3
4 1
Выходные данные
2
Входные данные
10
7 9
10 1
3 2
7 8
4 5
4 8
7 7
1 3
5 17
1 3
Выходные данные
3

Для отправки решений необходимо выполнить вход.

www.contester.ru