← 返回题目列表

Codeforces · 1561/C

C. 深处

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

在某个视频游戏中,玩家控制一个由单个整数值表征的英雄:力量。英雄必须击败同样具有单个整数值特征的怪物:护甲。

在当前关卡中,英雄面临着 $$$n$$$ 洞穴。要通过关卡,英雄必须按某种顺序进入所有洞穴,每个洞穴只进入一次,然后安全无恙地退出每个洞穴。当英雄进入洞穴$$$i$$$时,他将不得不连续与$$$k_i$$$怪物战斗:首先是一个有盔甲的怪物$$$a_{i, 1}$$$,然后是一个有盔甲的怪物$$$a_{i, 2}$$$等等,最后是一个有盔甲的怪物$$$a_{i, k_i}$$$。

当且仅当英雄的力量严格大于怪物的护甲时,英雄才能击败怪物。如果英雄无法击败他正在战斗的怪物,游戏就会结束,玩家就输了。请注意,一旦英雄进入洞穴,在严格按照给定的顺序与洞穴中的所有怪物战斗之前,他无法退出洞穴。

英雄每次击败怪物,英雄的力量都会增加$$$1$$$。

找到英雄开始关卡时必须具有的最小可能力量,以便能够按某种顺序进入所有洞穴并击败所有怪物。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 洞穴的数量。

接下来的 $$$n$$$ 行中的第 $$$i$$$ 包含一个整数 $$$k_i$$$ ($$$1 \le k_i \le 10^5$$$) — 第 $$$i$$$ 洞穴中的怪物数量,后跟 $$$k_i$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, k_i}$$$ ($$$1 \le a_{i, j} \le 10^9$$$) — 洞穴 $$$i$$$ 中怪物的护甲等级,英雄必须与它们战斗。

保证所有测试用例的$$$k_i$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 英雄开始关卡时必须具有的最小可能力量,以便能够按某种顺序进入所有洞穴并击败所有怪物。

示例

输入 #1

2
1
1 42
2
3 10 15 8
2 12 11

输出 #1

43
13

注意

在第一个测试用例中,英雄必须击败一个装甲为 $$$42$$$ 的怪物,拥有力量 $$$43$$$ 就足以实现这一目标。

在第二个测试用例中,英雄可以通过初始力量$$$13$$$的关卡,如下:

- 进入洞穴$$$2$$$:用盔甲$$$12$$$击败怪物,力量增加到$$$14$$$; 用盔甲击败怪物$$$11$$$,力量增加到$$$15$$$;
- 进入洞穴$$$1$$$:用盔甲$$$10$$$打败怪物,力量增加到$$$16$$$; 用盔甲击败怪物$$$15$$$,力量增加到$$$17$$$; 用盔甲击败怪物$$$8$$$,力量增加到$$$18$$$。