3213 - 奇怪的卡组

有一个奇怪的卡组,卡组从上到下放置着一些卡牌,每张卡牌有两个属性c,a。你每次可以选下列二种操作之一:

  • 选择打出卡组顶部的卡牌,并且根据卡牌的属性,把卡组顶部c张卡丢弃。(丢弃后不再使用)然后打出a的伤害。之后这张卡牌也被丢弃

  • 把顶部的卡牌放在卡组底部

进行若干次操作后,求一个卡组能够打出的最大伤害

输入

第一行一个数字n表示卡牌的数量

后面n行每行两个数字,表示第i张卡牌的两个属性,分别是c_i,a_i

输出

输出仅一个,即打出的所有卡牌伤害总和的最大值

样例

输入

5
1 1
1 1
1 1
2 5
1 2

输出

7

输入

15
8 2
4 4
6 1
7 8
8 10
1 8
6 7
2 4
9 6
8 4
4 7
8 5
10 7
4 6
6 10

输出

25

提示

0 < n \leq 1000, 0< a_i, c_i < n

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题