Описание

Ограничение по времени: 2000 ms
Ограничение по памяти: 512 Mb

Ответы на вопросы

Задача: Завоевание

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию
вошли все воины каждого из n городов его королевства. Петир выяснил, что в i-м городе ищут
работу ai воинов, которых он может завербовать в свою армию.
Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить
этому воину. Для вербовки одного воина из i-го города, необходимо заплатить ему ci золотых монет.
При этом воины из больших городов ценят свою работу дороже, поэтому если для i-го и j-го города
выполнено ai < aj , то ci ≤ cj .
Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в
какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось
в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен
заплатить воинам, чтобы все воины из всех городов оказались в его армии.

Формат входных данных
В первой строке входного файла находится целое число n (1 ≤ n ≤ 1000) — количество городов,
в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла
находится по два целых числа ai и ci (1 ≤ ai ≤ 100, 1 ≤ ci ≤ 10 000) — количество воинов в
i-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он
присоединился к армии. Для всех пар i и j выполнено условие, что если ai < aj , то ci ≤ cj .

Формат выходных данных
В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду
Петиру придется заплатить, чтобы все воины вошли в его армию.

Ввод:
3
1 1
2 2
4 3

Вывод: 5


В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит
2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились
к его армии.
Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из
первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится
4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.


Прикрепите файл с исходным кодом программы:
     
или введите исходный код на языке:


Правила оформления программ и список ошибок при автоматической проверке задач
           

Ваш ответ:

Загруженные файлы:


Нет

Примечание учителя: