HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Жадина

Section problems

• ЕГЭ — B1
• ЕГЭ — B1
• Евгений и Пикабу
• Евгений и задачи
• Евклидов граф
• Ежевика
• Ежевика
• Жадина
• Жадина
• Забор
• Забор
• 1
• Зарплата продукцией
• Звёздно-полосатый
• Игра с разрезанием
• Карта
• Кафе и такси

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/2000/2000/2000 ms. Memory limit 65536/65536/65536/65536 Kb.

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

Серьёзный бизнес Ивана по созданию на селе маршрутного такси не задался. Поэтому сейчас Иван на своём ЗИЛе-131 подвозит дачников на трассе между родным селом и областным центром.

Сейчас Иван едет из села в город. Дорогу можно представить как отрезок прямой, один конец которого (село) имеет координату 0, а другой конец (город) — координату X. На дороге находятся N дачников, i-й из которых хочет проехать от точки Ai до точки Bi (разумеется, в направлении от села к городу, так что Ai < Bi). Со всеми этими дачниками Иван давно знаком, поэтому заранее знает, откуда и куда нужно ехать каждому из них.

В кабине ЗИЛа есть место только для одного пассажира, поэтому подобрать следующего дачника Иван может только после того, как довезёт текущего. Удивительный факт: все дачники, вне зависимости от того, как далеко им нужно ехать, по старой дружбе платят Ивану одинаковую сумму за проезд. Иван — большой жадина, поэтому он размышляет, как именно ему нужно подбирать пассажиров, чтобы заработать как можно больше денег.

«Подбирать всегда, когда есть такая возможность!» — сделал вывод Иван. В самом деле, чем раньше посадишь пассажира, тем раньше его довезёшь и появится возможность посадить следующего, верно? Правда, в тот день ситуация на дороге оказалась следующей:

«Ладно, тогда будем подвозить тех, кто едет на наименьшее расстояние!» — суммировал Иван свой печальный опыт. Однако ему вновь не повезло:

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

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

Первая строка содержит целые числа X и N (10 ≤ X ≤ 1000, 0 ≤ N ≤ 100) — соответственно координату города и число дачников.

Следующие N строк описывают дачников. Каждая из них содержит целые числа Ai и Bi (0 ≤ Ai < Bi ≤ X) — соответственно координаты точки, в которой стоит i-й дачник, и точки, в которую ему нужно попасть.

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

Выведите одно целое число — максимальное количество дачников, которых Иван может подвезти по пути из села в город.

Примеры

Входные данные
10 3
1 2
4 8
3 7
Выходные данные
2
Входные данные
10 6
0 10
1 2
3 4
5 6
7 8
9 10
Выходные данные
5
Входные данные
10 3
0 5
4 7
6 10
Выходные данные
2
Для отправки решений необходимо выполнить вход.

www.contester.ru