In the Icpca Kingdom, two types of currency, coins and gems, are used. To buy a merchandise in shops in this kingdom, you pay either the number of coins shown on its price tag or only $$$1$$$ gem.
Today, the final day of your sightseeing trip to the Icpca Kingdom, you are visiting a souvenir shop to buy some bottles of local signature liquor. There are $$$n$$$ bottles of liquor in this shop. Each liquor is crafted by a different artisan, and therefore the prices may vary. Although you have enough number of coins, you'd like to buy all the $$$n$$$ bottles with the lowest possible amount of coins, appropriately using the unique benefits provided by the shop.
The detail of the unique benefits is as follows: for some of the bottles in this shop, a complimentary bag of some number of gems are attached to them. Therefore, buying some bottles using the bonus gems that are obtained at prior purchases may reduce the number of coins required.
Starting with no gems, what is the minimum number of coins required to buy all the $$$n$$$ bottles?
Figure E.1 describes the prices of the bottles and gems attached to them in the first test case of Sample Input 1. In this case, if you buy the first bottle for $$$400$$$ coins, you obtain one gem. Then, by buying the third, fourth, and second bottles in this order using gems, you can buy them all without paying any additional coins.
 |
| Figure E.1: The first test case of Sample Input 1 |
The input contains one or more test cases, each in the following format.
| $$$n$$$ |
| $$$a_{1}$$$ $$$b_{1}$$$ |
| $$$a_{2}$$$ $$$b_{2}$$$ |
| $$$\vdots$$$ |
| $$$a_{n}$$$ $$$b_{n}$$$ |
The integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ in the first line is the number of bottles in the souvenir shop. The $$$i$$$-th line of the next $$$n$$$ lines describes the information on the $$$i$$$-th bottle $$$(i = 1, 2, \dots, n)$$$. The integer $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$ is the number of coins on the price tag of the $$$i$$$-th bottle, and the integer $$$b_i$$$ $$$(0 \leq b_i \leq n)$$$ is the number of gems in the bag attached to the $$$i$$$-th bottle.
The end of the input is indicated by a line containing a zero. The number of test cases does not exceed $$$2500$$$. The sum of $$$n$$$ over all the test cases does not exceed $$$10^5$$$.
For each test case, output in a line the minimum number of coins required to buy all the $$$n$$$ bottles.
4400 1500 0600 1800 251540 01430 01320 01210 01100 020861 0901 0955 1602 1882 1188 1817 0932 2669 0621 2276 0668 0825 1834 1341 2545 0218 0939 0179 1587 10
400 6600 1747
