0391. Завоевание

Имя входного файла: conquest.in
Имя выходного файла: conquest.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из 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.

Формат выходного файла

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

Пример:

conquest.inconquest.out
3 1 1 2 2 4 3 5

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

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


Источник: Командное школьное первенство Республики Карелия. Ноябрь 2014.

Обсудить       Отправить решение



Версия для печати