在某个视频游戏中,玩家控制一个由单个整数值表征的英雄:力量。英雄必须击败同样具有单个整数值特征的怪物:护甲。
在当前关卡中,英雄面临着 $$$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$$$。