Minimizing Opponent's Score

In this problem, two players, Mingyue and Qingfeng, compete using chess pieces arranged on several independent battle lines. A battle line is a track along which pieces, once placed, will only move on that line. Each piece has a level, a positive integer assigned during the preparation phase. The only time these levels change is during a battle.

A battle happens as follows: When two pieces (one from each player) engage, if their levels are equal then both are eliminated; otherwise, the piece with the higher level has its level decreased by 1 and the lower‐level piece is eliminated. In every battle, at least one piece is eliminated.

The game consists of three phases:

1. Preparation Phase: Each player arranges pieces on n battle lines. For each battle line, a player can choose the number of pieces (possibly zero), and for each piece, the player selects its positive integer level as well as its order of appearance on that line.
2. Battle Phase: For each battle line, the following process is executed repeatedly until the line's battles conclude:
   • If both players have at least one piece remaining on the line, the earliest (i.e. first in order) remaining piece from each side engage in a battle.
   • If one side has no remaining pieces on the line while the other has some, the player with remaining pieces gains game points equal to the sum of the levels of those remaining pieces. The battle on that line then ends.
   • If neither side has any pieces on the line, the battle on that line ends.
3. Settlement Phase: After all battle lines are resolved, the accumulated game points for each player become their final score for that game.

In this game, Mingyue has already completed the preparation phase and her configuration on all n battle lines is known. Before finishing his own preparation, Qingfeng gets to see all of Mingyue's arrangements. Qingfeng now wants to design his own preparation scheme (that is, how many pieces to place on each battle line and with what levels) subject to the following constraint:

• All of Qingfeng's pieces must have positive integer levels and the sum of these levels over all battle lines must not exceed m.

Qingfeng’s goal is to minimize Mingyue’s final score at the end of the game. Note that if, on a battle line with Mingyue’s pieces, Qingfeng is able to cancel out all of Mingyue’s pieces via battles then Mingyue gains 0 points from that line. It turns out that the optimal strategy on any battle line is to try and completely cancel Mingyue’s pieces. One simple way to achieve cancellation on a battle line where Mingyue has k pieces with levels \(a_1, a_2, \dots, a_k\) (in order) is to use one Qingfeng piece with initial level \(X\) such that for every battle:

• For the first k-1 battles: \(X- (i-1) > a_i\) for \(1 \le i \le k-1\).
• For the last battle: \(X - (k-1) \ge a_k\) (a tie results in both pieces being eliminated).

The minimal such \(X\) is:

[ X = \max{a_1+1,, a_2+2,, \dots,, a_{k-1}+(k-1),, a_k+(k-1)}. ]

If Qingfeng uses a piece of level \(X\) on this battle line, the cost (in terms of the sum of the levels used) is \(X\), and the savings is that Mingyue loses all her points from that line, which is \(\sum_{i=1}^{k} a_i\). On any battle line where Mingyue places no pieces, no cost is needed and Mingyue gains 0 points.

Given that Qingfeng’s overall budget (the total sum of levels he may use) is m, he can choose a subset of battle lines on which to invest the necessary cost to cancel Mingyue’s pieces. If he does nothing on a battle line, Mingyue will score \(\sum a_i\) on that line. Thus, the problem reduces to a 0/1 knapsack: each battle line (with Mingyue’s pieces) is an item having:

• Cost: \(c = \max\{a_1+1, a_2+2, \dots, a_{k-1}+(k-1), a_k+(k-1)\}\).
• Value (saving): \(v = \sum_{i=1}^{k} a_i\).

If the total of Mingyue’s points over all battle lines is \(S\), and Qingfeng is able to cancel a collection of battle lines with total saving \(V\) (using cost at most m), then Mingyue’s final score will be \(S-V\). Your task is to compute this minimum final score of Mingyue for each independent game.

Input Format:

• The first line contains an integer \(T\) representing the number of test cases.
• For each test case, the first line contains two integers \(n\) and \(m\), where \(n\) is the number of battle lines and \(m\) is Qingfeng’s maximum allowed total level sum.
• Then for each battle line, there is a line beginning with an integer \(k\) (the number of pieces on that battle line for Mingyue), followed by \(k\) positive integers \(a_1, a_2, ..., a_k\) representing the levels (in order) of Mingyue’s pieces. If \(k = 0\), then no further integers follow on that line.

Output Format:

• For each test case, output a single integer: the minimum final score of Mingyue after all battles.

Constraints and Notes:

• All of Qingfeng’s pieces must have positive integer levels.
• The sum of the levels of all of Qingfeng’s pieces used (across all battle lines) must not exceed \(m\).
• You may assume that any optimal strategy involves either completely canceling the pieces on a battle line (by investing the required cost) or doing nothing on that line.

Example:

Input:
3
1 100
2 1 100
2 105
1 50
2 1 2
2 10
3 1 2 3
1 10

Explanation:
Test Case 1: n = 1, m = 100, and Mingyue has a single battle line with pieces [1, 100].
  - Total points on line = 1 + 100 = 101.
  - To cancel this line, Qingfeng needs a piece of level at least max(1+1, 100+1) = 101, but m = 100 so he cannot cancel it. Thus, Mingyue scores 101.

Test Case 2: n = 2, m = 105.
  - Battle line 1: [50] requires cost = 50 and saves 50 points.
  - Battle line 2: [1, 2] requires cost = max(1+1, 2+1) = 3 and saves 3 points.
  - Total saving if both lines are canceled is 50 + 3 = 53, and total cost is 53 which is \(\le m\). So Mingyue’s final score is (50+3) - 53 = 0.

Test Case 3: n = 2, m = 10.
  - Battle line 1: [1,2,3] requires cost = max(1+1, 2+2, 3+2) = 5 and saves 6 points.
  - Battle line 2: [10] requires cost = 10 and saves 10 points.
  - With m = 10, Qingfeng can only cancel battle line 1 (cost 5) leading to a saving of 6. Therefore, Mingyue’s final score is (6+10) - 6 = 10.

inputFormat

The input begins with an integer \(T\) (the number of test cases). Each test case starts with a line containing two integers \(n\) and \(m\) — the number of battle lines and Qingfeng’s maximum total level sum, respectively. This is followed by \(n\) lines; each line starts with an integer \(k\) (the number of pieces on that battle line for Mingyue), followed by \(k\) positive integers denoting the levels of Mingyue's pieces in order. If \(k=0\), then that battle line contains no pieces.

outputFormat

For each test case, output a single integer — the minimum final score of Mingyue.

sample

3
1 100
2 1 100
2 105
1 50
2 1 2
2 10
3 1 2 3
1 10

101
0
10

</p>