Алибаба
Али-Баба, любимый герой наших детских сказок, стремится стать бессмертным, чтобы и дальше радовать детей. Для этого он должен доказать свою способность к невероятным поступкам. У него есть n сокровищ (n ≤ 10000), каждое из которых находится в разных местах вдоль прямой дороги. Каждое сокровище имеет свой дедлайн, после которого оно исчезает. Али-Баба должен собрать все n сокровищ как можно быстрее. Поэтому ему нужно определить оптимальный порядок сбора сокровищ, чтобы успеть до их дедлайнов, начиная с наиболее выгодной позиции. У Али-Бабы есть список мест и дедлайнов для каждого сокровища. Место i расположено на расстоянии di от крайней левой точки дороги. Время, необходимое для сбора сокровища, считается мгновенным.
Али-Баба должен определить минимальное время, за которое он может собрать все сокровища.
Входные данные
Каждый набор данных во входных данных соответствует определенному набору сокровищ. Для каждого набора входные данные содержат количество сокровищ и список пар "место - дедлайн" в порядке возрастания расположений. Пробелы могут свободно встречаться между числами во входных данных. Входные данные корректны.
Выходные данные
Для каждого набора данных программа выводит результат в стандартный выход на отдельной строке. Решение представляется минимальным временем, за которое Али-Баба может собрать все сокровища до их исчезновения. Если это невозможно, выводится "No solution".