U519393 战略游戏

$L$ 和 $M$ 在玩一个奇怪的战略游戏。 $L$ 是攻方，$M$ 是守方。$M$ 有 $n$ 座城池，每座城池都有对应的战斗力，记作 $a_1,a_2,\ldots,a_n$。每次 $L$ 选择一座未毁坏的城池并将其攻下（一旦城池被选择，该城池一定会被攻下）； $M$ 并不能进行反攻或防守，而是选择自毁一些城池，单次只能自毁**任意 $k$ 座未毁坏的城池**。我们称一座城池是毁坏的，当且仅当这座城池被 $L$ 攻下或是被 $M$ 自毁。游戏采用回合制，记 $L$ 的一次攻击与 $M$ 的一次防守（也可以叫做自毁）为一个回合，$L$ 先发动攻击。等到所有城池全部被毁坏，游戏结束。 $L$ 的系统里有一个成就墙，假设 $L$ 攻下了城池 $x$，则会点亮成就墙的第 $a_x+1$ 个数（可以重复点亮，但并不会有额外效果）。而 $L$ 在一轮游戏中的得分为从左到右第一个没有被点亮的数的编号 $-1$ 后的值。 $L$ 希望自己的得分尽可能大， $Q$ 希望 $L$ 的得分尽可能小。请计算在该策略下 $L$ 的得分最大值。 **每当新一轮游戏开始，成就墙清空。**

第一行包含一个整数 $T$（$ 1 \leq T \leq 10^5 $），表示有 $T$ 轮游戏。 接下来描述每一轮游戏： 为了方便输入，给定城池攻击力最大值 $m$，然后给出 $f_i(0\leq i\leq m)$，表示 $i$ 这个数在 $a$ 中出现的次数。 第一行包含两个整数 $m$ 和 $ k $ （$ 1 \le m \le 2 \cdot 10^5, 1 \le k \le 10^9 $）。 第二行包含 $m+1$ 个整数 $ f_0, f_1, \ldots, f_m $ ( $ 1\le f_i \le 10^9 $ )。 保证 $\sum_{i=1}^T m_i \leq2\cdot 10^5$。

对于每一轮游戏，计算 $L$ 的最大得分。

在第四轮游戏中，$a=\{0,0,0,0,1,1,1,1,1\}$，最大得分的游戏策略： $Round 1:$ L 攻打 1 号城池，成就墙第 1 个格子被点亮。 Q 自毁 2、3、5 号城池。 $Round 2:$ L 攻打 6 号城池，成就墙第 2 个格子被点亮。 Q 自毁 4、7、8、9 号城池。 此时游戏结束，而成就墙第 $3$ 个格子未被点亮，答案为 $3-1=2$ ## 数据范围 对于前 $50\%$ 的数据，$m\leq 100$ 对于 $100\%$ 的数据，$m\leq 2\cdot 10^5$