P12398 「FAOI-R9」Battle at Dawn

Mr.Light is very good at inventing mini-games. Qingfeng likes to play chess with Mingyue. One day, they played a game called "Wisdom Chess: Battle at Dawn" invented by Mr.Light. they were so addicted to the game's fun that they couldn't stop. Unfortunately, Mingyue was too smart so that Qingfeng was always defeated by Mingyue. So, he decided to pass this problem on to you to help him study it.

The definitions of some concepts are as follows: - Battle line: A track where the chess pieces are arranged in the order given by the player. **Once a chess piece lands on a battle line, it must move on this battle line.** - Chess piece level: The level assigned to a chess piece by the player, which will only change due to the result of a "battle". **Initially, this level must be a positive integer.** - Battle: In a battle between two chess pieces, when the levels of the two chess pieces are equal, both chess pieces are eliminated; when the levels of the two chess pieces are not equal, the level of the chess piece with the higher level is reduced by $1$, and the chess piece with the lower level is eliminated. In one battle, obviously at least one chess piece will be eliminated. The game process is as follows: - Initially, the game scores of both players are $0$. - **Preparation stage**: Both players specify the number of their own chess pieces, the level of each chess piece, the battle line it belongs to, and the order of appearance. **Note that it is possible not to place any chess pieces on a certain battle line.** - **Battle stage**: For each battle line, the following process is carried out (note that here, "active chess pieces" refer to the chess pieces that have not been eliminated **on this battle line**): - If neither side has any active chess pieces, the process for this battle line ends. - If one side has no active chess pieces, the other side gets a game score equal to the sum of the levels of the active chess pieces, and the process for this battle line ends. - If both sides have active chess pieces, the two chess pieces with the earliest order of appearance on both sides have a "battle". - **Settlement stage**: After the processes of all battle lines are completed, the game scores of the two players are the results of this game. In this game, there are $n$ battle lines. Mingyue has completed his preparation stage, but Qingfeng secretly saw Mingyue's preparation plans for all $n$ battle lines before he completed his own preparation. Please help Qingfeng design a preparation plan so that the initial levels of all of Qingfeng's chess pieces are positive integers and their sum does not exceed $m$, and Mingyue's game score is minimized after the game ends. You only need to output this minimum score. Since Qingfeng loves playing very much, you need to give answers for $T$ independent rounds of the game in total.

The first line contains two integers $T$ and $n$, representing the number of data sets and the number of battle lines in each game. For each data set: The first line contains an integer $m$, representing the upper limit of the sum of the levels of Qingfeng's chess pieces in this game. In the following $n$ lines, the $i$-th line starts with an integer $l_i$ representing the number of chess pieces arranged by Mingyue on this battle line, followed by $l_i$ integers, representing the level of each chess piece that appears in the Mingyue's camp in sequence(the order of appearance of the $l_i$ chess pieces is the order of their input).

For each data set, output a single line containing an integer representing the answer required by the problem.

#### Sample Description For the first test case: one possible plan is for Qingfeng to send out one chess piece with an initial level of $2$. The battle process is as follows: - The levels of Qingfeng's active chess pieces are $\{2\}$, and the levels of Mingyue's active chess pieces are $\{1,1\}$. The Qingfeng's chess piece with level 2 battles with Mingyue's chess piece with level 1. Mingyue's chess piece is eliminated, and the level of Qingfeng's chess piece is reduced to 1. - The levels of Qingfeng's active chess pieces are $\{1\}$, and the levels of Mingyue's active chess pieces are $\{1\}$. Both sides send out chess pieces with level 1 to battle, and both are eliminated. - Both sides have no more chess pieces, and this battle line does not affect the scores of both sides. Therefore, Mingyue's score in this plan is $0$. #### Constraints **Subtasks are used in this problem.** | Subtask ID | $ n $ | $ l_i $ | $ m $ | max level of Mingyue's chess pieces | points | |:-:|:-:|:-:|:-:|:-:|:-:| | $ 1 $ | $ =1 $ | $ \le 5 $ | $ \le 10 $ | $ \le 5 $ | $ 8 $ | | $ 2 $ | $ =1 $ | $ \le 300 $ | $ \le 300 $ | $ \le 5 $ | $ 16 $ | | $ 3 $ | $ =1 $ | - | - | $ =1 $ | $ 4 $ | | $ 4 $ | $ =1 $ | - | - | - | $ 24 $ | | $ 5 $ | $ =2 $ | - | $ =0 $ | - | $ 4 $ | | $ 6 $ | $ =2 $ | $ \le 300 $ | - | - | $ 8 $ | | $ 7 $ | $ =2 $ | $ \le 5000 $ | - | - | $ 12 $ | | $ 8 $ | $ =2 $ | - | - | - | $ 24 $ | For all test cases: - $1\le T\le 5$; - $\bm{1 \le n\le 2}$, $1\le l_i\le 10^5$； - $0\le m\le 10^{18}$. The level of Mingyue's chess pieces are all positive integers and do not exceed $10^9$.