Problem D: PIPI买宝石

Problem D: PIPI买宝石

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 125  Solved: 18
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI进了一家宝石店,里面有n块宝石,每块宝石的价值为xi,但是如果买了第i块宝石,他购买的总宝石数量就不能超过yi。
PIPI的资金十分足够,请问他能买到的宝石的总价值最大为多少?

Input

多组输入。
第一行输入宝石的数量n(1<=n<=1e4)。
接下来n行分别输入第i块宝石的价值和数量限制(0<=xi<=1e9,1<=yi<=n)。

Output

输出PIPI能买到的宝石最大总价值

Sample Input

2
2 1
3 2

Sample Output

3

HINT

只能买第二块,因为如果两块都买,会违反第一块的数量要求