시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.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$.

출력

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

예제 입력 1

3
1 1
2 2
4 3

예제 출력 1

5

힌트

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

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