您正在玩一款名为 Splay the Sire 的电脑纸牌游戏。目前你正在努力击败游戏的最终boss。
boss战由$$$n$$$回合组成。在每个回合中,您都会获得几张卡牌。每张卡牌都有两个参数:成本 $$$c_i$$$ 和伤害 $$$d_i$$$。您可以在每个回合中按某种顺序打出一些牌(您选择牌及其打出的确切顺序),只要您在该回合中打出的牌的总成本不超过 $$$3$$$。打出一些(可能是零张)牌后,您结束回合,并且所有未打出的牌都将被丢弃。请注意,每张卡最多可以使用一次。
你的角色还发现了一件神器,可以提高你的某些行动的伤害:你打出的每张$$$10$$$卡都会造成双倍伤害。
在 $$$n$$$ 回合中你能造成的最大伤害是多少?
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 圈数。
然后是 $$$n$$$ 输入块,第 $$$i$$$ 块代表你在第 $$$i$$$ 回合中获得的牌。
每个块都以包含一个整数 $$$k_i$$$ 的行开始 ($$$1 \le k_i \le 2 \cdot 10^5$$$) — 您在第 $$$i$$$ 回合中获得的牌数。接下来是 $$$k_i$$$ 行,每行包含两个整数 $$$c_j$$$ 和 $$$d_j$$$ ($$$1 \le c_j \le 3$$$, $$$1 \le d_j \le 10^9$$$) — 相应卡的参数。
保证 $$$\sum \limits_{i = 1}^{n} k_i \le 2 \cdot 10^5$$$。
输出
打印一个整数——你可能造成的最大伤害。
示例
输入 #1
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
输出 #1
263
注意
在示例测试中,最佳操作方案如下:
在第一回合中,以任意顺序打出所有三张牌并造成 $$$18$$$ 伤害。
在第二回合中,打出两张牌并造成 $$$7$$$ 伤害。
在第三回合中,打出第一张和第三张牌并造成 $$$13$$$ 伤害。
在第四回合中,打出第一张和第三张牌并造成 $$$25$$$ 伤害。
在第五回合中,打出唯一一张牌,它将造成双倍伤害($$$200$$$)。