← 返回题目列表

Codeforces · 1176/F

F. 摧毁它!

中文机器翻译题面 查看原题

您正在玩一款名为 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$$$)。