题目背景

牢光是一个很会发明小游戏的人。

清风喜欢和明月玩棋。有一天，他玩了一款牢光发明的《智棋之决战黎明》，因为游戏的趣味而欲罢不能，可惜明月太聪明了，他总是被明月虐。于是，他决定把这个问题推给你让你帮他研究。

题目描述

一些概念的定义如下：

• 战线：棋子按照玩家给定的顺序排列的轨道，棋子一旦落入战线，即必须在这个战线上行动。

• 棋子等级：玩家给棋子赋予的等级，会且只会因为「对战」的结果产生变化。初始时这个等级必须为正整数。

• 对战：对于两个棋子的对战，当棋子等级相等时，两个棋子均被消除；当两个棋子等级不等时，等级大的棋子等级减少 $1$，等级小的棋子被消除。在一次对战中，显然至少会消除掉 $1$ 个棋子。

游戏流程如下：

• 初始时双方游戏积分均为 $0$。

• 准备阶段：双方玩家规定本方的棋子数量，每个棋子的棋子等级、所属战线和出场顺序。注意可以在某条战线上不放置任何棋子。

• 对战阶段：对于每条战线，进行如下流程（注意这里「在场棋子」指本条战线上未被消除的棋子）：

  • 如果两方均没有在场的棋子，则这个战线的流程结束。

  • 如果一方已经没有在场的棋子，则另一方获得与在场棋子的等级之和相等的游戏积分，这个战线的流程结束。

  • 如果双方均有在场的棋子，则两方在场的出场顺序最靠前的棋子进行一次「对战」。

• 结算阶段：当所有战线的流程结束后，两个玩家的游戏积分则为本次游戏的结果。

在本局游戏中，有 $n$ 个战线。

明月已经完成了自己的准备阶段，但是清风在自己未完成准备时偷偷看到了明月的全部 $n$ 个战线的准备方案。

请你帮助清风设计一种准备方案，使得清风的所有棋子的初始等级均为正整数且和不超过 $m$，且游戏结束后明月的游戏积分最少，你只需要输出这个最少的积分量即可。

因为清风很爱玩，所以你总共要对于 $T$ 轮各自独立的游戏给出答案。

输入格式

第一行两个整数 $T,n$，代表数据组数和每局游戏的战线条数。

对于每组数据：

第一行一个整数 $m$，代表本局游戏清风的棋子等级之和上限。

接下来 $n$ 行的第 $i$ 行，每行开头一个整数 $l_i$ 代表这个战线明月排布的棋子数量，接下来 $l_i$ 个整数，依次表示明月阵营出场的每个棋子的等级（$l_i$ 个棋子的出场顺序即为它们的读入顺序）。

输出格式

对于每组数据，输出一行一个整数，代表题目要求的答案。

5 1
2
2 1 1
2
3 1 1 1
3
4 4 3 2 1
7
5 4 3 6 2 1
101
10 10 100 10 100 10 10 10 100 10 10

0
1
7
6
260

3 2
10
1 7
3 1 5 1
14
8 4 3 2 1 4 3 2 1
8 4 3 2 1 4 3 2 1
13
5 4 3 8 7 1
6 3 5 4 3 2 1

4
9
14

提示

【样例 1 解释】

对于第一组数据，一种方案是清风派出初始等级为 $2$ 的棋子一枚。

对战流程如下：

• 清风在场棋子等级分别为 $\{2\}$，明月在场棋子等级分别为 $\{1,1\}$，等级为 $2$ 的清风棋子和等级为 $1$ 的明月棋子对战，明月棋子被消除，清风棋子等级降为 $1$。

• 清风在场棋子等级分别为 $\{1\}$，明月在场棋子等级分别为 $\{1\}$，双方均派出等级为 $1$ 的棋子出战，均被消除。

• 双方均已无棋子，该条战线不影响双方积分。

因此，该种方案明月的积分为 $0$。

【数据规模与约定】

本题采用捆绑测试。

对于每个测试点：

• $1 \le T \le 5$；

• $\bm{1 \le n \le 2}$，$1 \le l_i \le 10^5$；

• $0 \le m \le 10^{18}$，明月的棋子等级均为正整数且不超过 $10^9$。

子任务编号	$n$	$l_i$	$m$	明月棋子等级上限	分值
$1$	$=1$	$\le 5$	$\le 10$	$\le 5$	$8$
$2$		$\le 300$			$16$
$3$		-	-	$=1$	$4$
$4$				-	$24$
$5$	$=2$		$=0$		$4$
$6$		$\le 300$	-		$8$
$7$		$\le 5000$			$12$
$8$		-			$24$