P83213

奇怪的卡组

难度 6 级 初三 动态规划入门 背包
讨论 统计 5通过 12提交 41.7%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

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

  • 选择打出卡组顶部的卡牌,并且根据卡牌的属性,把卡组顶部c张卡丢弃。(丢弃后不再使用)然后打出a的伤害。之后这张卡牌也被丢弃。当然,你需要保证卡组内有c+1张卡牌

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

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

输入

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

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

输出

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

样例

样例 1
输入
5
1 1
1 1
1 1
2 5
1 2
输出
7
样例 2
输入
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

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交