시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 4 | 1 | 1 | 25.000% |
Лорд Петир собирает армию для похода на соседнее королевство. Он хочет, чтобы в его армию вошли все воины каждого из $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$.
В выходной файл выведите одно целое число --- минимальное количество монет, которые Лорду Петиру придется заплатить, чтобы все воины вошли в его армию.
3 1 1 2 2 4 3
5
В приведенном примере Лорду необходимо действовать следующим образом. Сначала он платит 2 монеты воину из второго города, и 3 монеты воину из третьего города, чтобы они присоединились к его армии.
Теперь в армии Лорда 2 воина, а в городах осталось 1, 1 и 3 воина, соответственно. Воины из первого и второго городов бесплатно присоединяются к армии Лорда Петира, в его армии становится 4 воина, после чего и оставшиеся 3 воина из третьего города бесплатно присоединяются к его армии.