Kamil finished his final exams, but he's not happy with his grades. He wants to change his grade for subjects. Each teacher will change his grade for a price: The th teacher will do this for coins. The teachers have a deal: The th teacher will correct Kamil's grade for free if Kamil bribes at least other teachers.
Kamil wants to know the minimum amount of coins he needs to bribe his teachers to change his grades.
Input Format
The first line of input contains one integer number : the number of different subjects.
The next lines contain two integers and : the coins needed to bribe -th teacher and the minimum number of teachers which Kamil must bribe so that th teacher changes his grade for free, respectively.
Constraints
For full score
In 20% of testcases
Output Format
In a single line, print one integer number: the minimum amount of coins required to change the grade for all subjects.
Sample Input 1:
2
3 0
2 1
Sample Output 1:
2
Sample Input 2:
4
1 1
3 1
4 1
9 3
Sample Output 2:
8
Explanation
In the first sample, there are 2 subjects. The first teacher will change Kamil’s grade if he gives them 3 coins. The second teacher will change Kamil’s grade if he gives them 2 coins OR bribes at least 1 other teacher. His optimal solution is to bribe the second teacher with 2 coins, and the first teacher will change his grade for free. Answer: 2 coins.
In the second sample, the optimal solution is to bribe the first three teachers so that the most expensive teacher will change for free. Kamil will spend coins.