B. Жадина

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

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

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

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

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

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