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

Разделы > Неотсортированные > задача:


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

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

Задачи раздела

• Количество дней в месяце
• Количество путей
• Коробки с соком
• Красивые часы — 1
• Лучше, чем приоритетная очередь
• Макс и ДНК
• Макс и СНИЛС
• Макс и автоконтраст
• Макс и аттракционы
• Макс и борьба с вирусом --- 2
• Макс и взрывоопасные зелья
• Макс и вороны
• Макс и выбор операции
• Макс и гирлянда
• Макс и две маршрутки
• Макс и дегустация сыра
• Макс и дегустация сыра

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

Если у вас есть предложения или пожелания по работе 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