13043: 【原3043】铁索连环

author: 董博男原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3043

Description

默默最近迷上了三国杀。三国杀是一种桌游，说的是三个国家之间的打打杀杀。

默默这几天在玩一种奇怪的类三国杀游戏。这个游戏是这样的：

有n个武将排成一排，这其中有的是忠臣，有的是反贼。

作为主公的你，可以每一轮把连续k个血量都大于等于k的人用铁索连起来，这样这一轮被连起来的k个人每人会受到k点伤害。

每人只能被铁索连一次。经过足够轮之后，主公得到的奖励值为对反贼的伤害总点数减去对忠臣的伤害总点数。

默默希望你能帮她解决这个有趣的问题，也就是给出主公能得到的最大的奖励值。

第一行是一个整数n表示n个武将，n是1到10000范围内的整数。

以下n行每行两个整数x，y依次顺序表示每个武将的身份和血量。x＝0为忠臣；x＝1为反贼。y是0到1000之间的整数。

输出只有一行，包含一个整数表示主公能得到的最大的奖励值。

40% 1<=n<=20
60% 1<=n<=1000
100% 1<=n<=10,000

尝试利用递推或者递归解题。

Time limit: 1000ms, memory limit: 50000kb.

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！