P12398 「FAOI-R9」决战黎明

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

一些概念的定义如下： * 战线：棋子按照玩家给定的顺序排列的轨道，**棋子一旦落入战线，即必须在这个战线上行动**。 * 棋子等级：玩家给棋子赋予的等级，会且只会因为「对战」的结果产生变化。**初始时这个等级必须为正整数。** * 对战：对于两个棋子的对战，当棋子等级相等时，两个棋子均被消除；当两个棋子等级不等时，等级大的棋子等级减少 $ 1 $，等级小的棋子被消除。在一次对战中，显然至少会消除掉 $ 1 $ 个棋子。 游戏流程如下： * 初始时双方游戏积分均为 $ 0 $。 * **准备阶段**：双方玩家规定本方的棋子数量，每个棋子的棋子等级、所属战线和出场顺序。**注意可以在某条战线上不放置任何棋子。** * **对战阶段**：对于每条战线，进行如下流程（注意这里「在场棋子」指**本条战线上**未被消除的棋子）： * 如果两方均没有在场的棋子，则这个战线的流程结束。 * 如果一方已经没有在场的棋子，则另一方获得与在场棋子的等级之和相等的游戏积分，这个战线的流程结束。 * 如果双方均有在场的棋子，则两方在场的出场顺序最靠前的棋子进行一次「对战」。 * **结算阶段**：当所有战线的流程结束后，两个玩家的游戏积分则为本次游戏的结果。 在本局游戏中，有 $ n $ 个战线。 明月已经完成了自己的准备阶段，但是清风在自己未完成准备时偷偷看到了明月的全部 $ n $ 个战线的准备方案。 请你帮助清风设计一种准备方案，使得清风的所有棋子的初始等级均为正整数且和不超过 $ m $，且游戏结束后明月的游戏积分最少，你只需要输出这个最少的积分量即可。 因为清风很爱玩，所以你总共要对于 $ T $ 轮各自独立的游戏给出答案。

无

无

**【样例 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 $ | $ =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 $ |