CF1561C.Deep Down Below

在某款视频游戏中，玩家控制的英雄由一个整数值“力量”来描述。英雄需要击败怪物，每个怪物也由一个整数值“护甲”来描述。

在当前关卡中，英雄面对 $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$ 个洞穴中怪物的护甲值，英雄必须按顺序依次战斗。

保证所有测试用例中 $\sum k_i \le 10^5$。

对于每组测试数据，输出一个整数，表示英雄能够通关所需的最小初始力量。

在第一个测试用例中，英雄只需击败一个护甲为 $42$ 的怪物，初始力量为 $43$ 即可。

在第二个测试用例中，英雄可以以初始力量 $13$ 通关，顺序如下：

• 先进入第 $2$ 个洞穴：
  • 击败护甲为 $12$ 的怪物，力量变为 $14$；
  • 击败护甲为 $11$ 的怪物，力量变为 $15$；
• 再进入第 $1$ 个洞穴：
  • 击败护甲为 $10$ 的怪物，力量变为 $16$；
  • 击败护甲为 $15$ 的怪物，力量变为 $17$；
  • 击败护甲为 $8$ 的怪物，力量变为 $18$。

由 ChatGPT 4.1 翻译