牛娃正在玩一款名为“八字魔王”的电脑纸牌游戏。
经过长时间的努力,牛娃终于看到了胜利的曙光。现在,牛娃正在努力击败游戏的最终boss。
boss战斗包含n个回合。 在每个回合中,牛娃将获得若干张纸牌。每张纸牌都有两个参数:代价ci和伤害di。
牛娃可以在每个回合中按照一定的顺序使用一些纸牌(牛娃可以自己决定选择哪些纸牌以及它们的使用顺序),只要牛娃在该回合中使用的纸牌的总代价不超过3就可以。
在玩了一些纸牌(可能是零)后,牛娃结束了该回合,所有牛娃没有玩的纸牌都被丢弃。 请注意每张纸牌最多只能使用一次。也就是说,在游戏的每个回合,牛娃可以选择总代价不超过3 的若干张纸牌攻击boss,其他未使用的纸牌都会被舍弃。
在游戏过程中系统还赠送给牛娃一个神器,可以提高牛娃的一些行动的伤害:牛蛙每玩10张牌,该牌可以对boss造成双倍伤害。
请问,在n个回合的boss战中,牛娃对boss所能造成的最大伤害是多少? 聪明的你请帮助牛娃算算看吧。
第一行包含一个整数n(1≤n≤2×105),表示游戏的回合数。
接下来是n个输入块,第i个输入块代表牛娃在第i轮中得到的牌。
每个输入块都以一行开始,该行包含一个整数ki(1≤ki≤2×105):在第i轮中获得的纸牌数。
然后是ki行,每行包含两个整数cj和dj(1≤cj≤3,1≤dj≤109):第j张纸牌的两个参数(cj表示纸牌的代价,dj表示纸牌对boss造成的伤害)。
测试数据保证: 纸牌的总数≤2×10
5
请注意:
在上述样例中,最佳行动方案如下:
在第一个回合中,以任意顺序使用所有三张牌并造成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