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 65000/65000/65000/65000 Kb.

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

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

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

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

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

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

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

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

Далее следуют N строк, i-я из которых содержит целые числа 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