Задача №113623. Завоевание
Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из \(n\) городов его королевства. Петир выяснил, что в \(i\)-м городе ищут работу \(a_i\) воинов, которых он может завербовать в свою армию.
Исходно в армии Лорда нет ни одного воина. Чтобы воин вошел в армию, Петир может заплатить этому воину. Для вербовки одного воина из \(i\)-го города, необходимо заплатить ему \(c_i\) золотых монет. При этом воины из больших городов ценят свою работу дороже, поэтому если для \(i\)-го и \(j\)-го города выполнено \(a_i < a_j\), то \(c_i \le c_j\).
Однако есть еще один способ добиться того, чтобы воины присоединились к армии. Если в какой-то момент оказывается, что в армии Лорда Петира уже строго больше воинов, чем осталось в некотором городе, то все воины этого города бесплатно присоединяются к армии Лорда.
Помогите Лорду Петиру выяснить, какое минимальное количество золотых монет он должен заплатить воинам, чтобы все воины из всех городов оказались в его армии.
В первой строке входного файла находится целое число \(n\) (\(1 \le n \le 1000\)) — количество городов, в которых Лорд Петир намерен набирать себе воинов. В следующих n строках входного файла находится по два целых числа \(a_i\) и \(c_i\) (\(1 \le a_i \le 100, 1 \le c_i \le 10 000\)) — количество воинов в \(i\)-м городе и число монет, которое необходимо заплатить одному воину в этом городе, чтобы он присоединился к армии. Для всех пар \(i\) и \(j\) выполнено условие, что если \(a_i < a_j\), то \(c_i \le c_j\).
В выходной файл выведите одно целое число — минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.
В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились к его армии.
Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.
3 1 1 2 2 4 3
5