《技术》学考及选考相关问题请联系张博士13958083702(手机和微信同号) 问题 5027 --牛娃打boss

5027: 牛娃打boss

时间限制: 1 Sec  内存限制: 128 MB
提交: 8  解决: 4
[提交][状态][命题人:]

题目描述

牛娃正在玩一款名为“八字魔王”的电脑纸牌游戏。 经过长时间的努力,牛娃终于看到了胜利的曙光。现在,牛娃正在努力击败游戏的最终boss。  

boss战斗包含n个回合。 在每个回合中,牛娃将获得若干张纸牌。每张纸牌都有两个参数:代价ci和伤害di。 牛娃可以在每个回合中按照一定的顺序使用一些纸牌(牛娃可以自己决定选择哪些纸牌以及它们的使用顺序),只要牛娃在该回合中使用的纸牌的总代价不超过3就可以。 在玩了一些纸牌(可能是零)后,牛娃结束了该回合,所有牛娃没有玩的纸牌都被丢弃。 请注意每张纸牌最多只能使用一次。也就是说,在游戏的每个回合,牛娃可以选择总代价不超过3 的若干张纸牌攻击boss,其他未使用的纸牌都会被舍弃。

在游戏过程中系统还赠送给牛娃一个神器,可以提高牛娃的一些行动的伤害:牛蛙每玩10张牌,该牌可以对boss造成双倍伤害。

      请问,在n个回合的boss战中,牛娃对boss所能造成的最大伤害是多少?  聪明的你请帮助牛娃算算看吧。

输入

第一行包含一个整数n(1n2×105),表示游戏的回合数。 

 

接下来是n个输入块,第i个输入块代表牛娃在第i轮中得到的牌。 

 

每个输入块都以一行开始,该行包含一个整数ki(1ki2×105):在第i轮中获得的纸牌数。

然后是ki行,每行包含两个整数cjdj(1cj3,1dj109):第j张纸牌的两个参数(cj表示纸牌的代价,dj表示纸牌对boss造成的伤害)。 

测试数据保证: 纸牌的总数≤2×105

输出

一个整数:牛娃对boss可能造成的最大伤害。
样例输入
Copy
5  
3  
1 6  
1 7  
1 5  
2  
1 4  
1 3  
3  
1 10
3 5  
2 3  
3 
1 15  
2 4  
1 10  
1  
1 100 
样例输出
Copy
263

提示

请注意:

在上述样例中,最佳行动方案如下:  

在第一个回合中,以任意顺序使用所有三张牌并造成18点伤害。

在第二回合中,使用两张牌并造成7点伤害。

在第三回合中,打出第一张和第三张牌并造成13点伤害。

在第四回合中,打出第一张和第三张牌并造成25点伤害。

在第五回合中,打出唯一一张并对boss造成双倍伤害(200)的牌。

总的伤害值为:18+7+13+25+200=263 

再给小童鞋们一组测试数据:

输入3

1

4

1 1

1 1

2 2

3 4

输出3

4

来源

 

[提交][状态]

如有问题,请咨询客服
浙ICP备20001167号