311166: CF1943E1. MEX Game 2 (Easy Version)

E1. MEX Game 2 (Easy Version)time limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the easy version of the problem. The only difference between the two versions is the constraint on $t$, $m$ and the sum of $m$. You can make hacks only if both versions of the problem are solved.

Alice and Bob play yet another game on an array $a$ of size $n$. Alice starts with an empty array $c$. Both players take turns playing, with Alice starting first.

On Alice's turn, she picks one element from $a$, appends that element to $c$, and then deletes it from $a$.

On Bob's turn, he picks at most $k$ elements from $a$, and then deletes it from $a$.

The game ends when the array $a$ is empty. Alice's score is defined to be the MEX$^\dagger$ of $c$. Alice wants to maximize her score while Bob wants to minimize it. Find Alice's final score if both players play optimally.

The array will be given in compressed format. Instead of giving the elements present in the array, we will be giving their frequencies. Formally, you will be given $m$, the maximum element in the array, and then $m + 1$ integers $f_0, f_1, \ldots, f_m$, where $f_i$ represents the number of times $i$ occurs in the array $a$.

$^\dagger$ The $\operatorname{MEX}$ (minimum excludant) of an array of integers is defined as the smallest non-negative integer which does not occur in the array. For example:

• The MEX of $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$, because $0$, $1$, $2$ and $3$ belong to the array, but $4$ does not.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $m$ and $k$ ($1 \le m \le 50, 1 \le k \le 10^9$).

The second line contains $m + 1$ integers $f_0, f_1, \ldots, f_m$ ($1 \le f_i \le 10^9$).

It is guaranteed the sum of $m$ over all test cases does not exceed $1000$.

Output

For each test case, find Alice's score if both players play optimally.

ExampleInput

5
1 4
4 5
2 1000000000
1000000000 1000000000 1000000000
3 2
2 3 100 1
1 1
2 2
3 1
1 1 1 1

Output

2
1
3
2
1

Note

In the first test case, the array $a$ is $[0, 0, 0, 0, 1, 1, 1, 1, 1]$. A possible game with a score of $2$ is as follows:

1. Alice chooses the element $0$. After this move, $a = [0, 0, 0, 1, 1, 1, 1, 1]$ and $c=[0]$.
2. Bob chooses to remove the $3$ elements $0$, $0$ and $1$. After this move, $a = [0, 1, 1, 1, 1]$ and $c=[0]$.
3. Alice chooses the element $1$. After this move, $a = [0,1,1,1]$ and $c=[0,1]$.
4. Bob removes the $4$ remaining elements $0$, $1$, $1$ and $1$. After this move, $a=[\,]$ and $c=[0,1]$.

At the end, $c=[0,1]$ which has a MEX of $2$. Note that this is an example game and does not necessarily represent the optimal strategy for both players.

In the second test case, Alice can choose a $0$ in her first turn, guaranteeing that her score is at least $1$. While Bob can remove all copies of element $1$ in his first turn, thus guaranteeing that Alice's score cannot exceed $1$. So Alice's score is $1$ if both players play optimally.

题目大意：

这是一个关于爱丽丝和鲍勃在数组上进行游戏的题目。数组a的初始大小为n，爱丽丝从一个空数组c开始。两位玩家轮流进行游戏，爱丽丝先开始。

在爱丽丝的回合，她从数组a中选择一个元素，将其添加到数组c中，然后从数组a中删除它。

在鲍勃的回合，他从数组a中选择至多k个元素，然后从数组a中删除它们。

当数组a为空时，游戏结束。爱丽丝的得分被定义为数组c的MEX值。爱丽丝希望最大化她的得分，而鲍勃希望最小化得分。如果两位玩家都发挥最佳，求爱丽丝的最终得分。

数组将以压缩格式给出。不是直接给出数组中存在的元素，而是给出它们的出现频率。具体来说，将给出m（数组中的最大元素）和m+1个整数f0, f1, ..., fm，其中fi表示i在数组a中出现的次数。

MEX（最小排除数）的定义是：一个整数数组中最小的非负整数，它不在数组中。例如：

- [2,2,1]的MEX是0，因为0不在数组中。
- [3,1,0,1]的MEX是2，因为0和1在数组中，但2不在。
- [0,3,1,2]的MEX是4，因为0、1、2和3在数组中，但4不在。

输入输出数据格式：

输入：

每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤500）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数m和k（1≤m≤50，1≤k≤10^9）。

第二行包含m+1个整数f0, f1, ..., fm（1≤fi≤10^9）。

保证所有测试用例的m之和不超过1000。

输出：

对于每个测试用例，如果两位玩家都发挥最佳，输出爱丽丝的得分。题目大意： 这是一个关于爱丽丝和鲍勃在数组上进行游戏的题目。数组a的初始大小为n，爱丽丝从一个空数组c开始。两位玩家轮流进行游戏，爱丽丝先开始。 在爱丽丝的回合，她从数组a中选择一个元素，将其添加到数组c中，然后从数组a中删除它。 在鲍勃的回合，他从数组a中选择至多k个元素，然后从数组a中删除它们。 当数组a为空时，游戏结束。爱丽丝的得分被定义为数组c的MEX值。爱丽丝希望最大化她的得分，而鲍勃希望最小化得分。如果两位玩家都发挥最佳，求爱丽丝的最终得分。 数组将以压缩格式给出。不是直接给出数组中存在的元素，而是给出它们的出现频率。具体来说，将给出m（数组中的最大元素）和m+1个整数f0, f1, ..., fm，其中fi表示i在数组a中出现的次数。 MEX（最小排除数）的定义是：一个整数数组中最小的非负整数，它不在数组中。例如： - [2,2,1]的MEX是0，因为0不在数组中。 - [3,1,0,1]的MEX是2，因为0和1在数组中，但2不在。 - [0,3,1,2]的MEX是4，因为0、1、2和3在数组中，但4不在。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤500）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数m和k（1≤m≤50，1≤k≤10^9）。 第二行包含m+1个整数f0, f1, ..., fm（1≤fi≤10^9）。 保证所有测试用例的m之和不超过1000。 输出： 对于每个测试用例，如果两位玩家都发挥最佳，输出爱丽丝的得分。