Серьёзный бизнес Ивана по созданию на селе маршрутного такси не задался. Поэтому сейчас Иван на своём ЗИЛе-131 подвозит дачников на трассе между родным селом и областным центром.
Сейчас Иван едет из села в город. Дорогу можно представить как отрезок прямой, один конец которого (село) имеет координату 0, а другой конец (город) — координату X. На дороге находятся N дачников, i-й из которых хочет проехать от точки Ai до точки Bi (разумеется, в направлении от села к городу, так что Ai < Bi). Со всеми этими дачниками Иван давно знаком, поэтому заранее знает, откуда и куда нужно ехать каждому из них.
В кабине ЗИЛа есть место только для одного пассажира, поэтому подобрать следующего дачника Иван может только после того, как довезёт текущего. Удивительный факт: все дачники, вне зависимости от того, как далеко им нужно ехать, по старой дружбе платят Ивану одинаковую сумму за проезд. Иван — большой жадина, поэтому он размышляет, как именно ему нужно подбирать пассажиров, чтобы заработать как можно больше денег.
«Подбирать всегда, когда есть такая возможность!» — сделал вывод Иван. В самом деле, чем раньше посадишь пассажира, тем раньше его довезёшь и появится возможность посадить следующего, верно? Правда, в тот день ситуация на дороге оказалась следующей:
«Ладно, тогда будем подвозить тех, кто едет на наименьшее расстояние!» — суммировал Иван свой печальный опыт. Однако ему вновь не повезло:
В расстроенных чувствах Иван обратился за помощью к вам. Может быть, вы сможете вывести правило, по которому нужно подвозить дачников, чтобы получить наибольшее количество денег.