E1. MEX игра - 2 (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это простая версия задачи. Единственное различие между двумя версиями заключается в ограничениях на $$$t$$$, $$$m$$$ и сумму $$$m$$$. Вы можете делать взломы, только если обе версии задачи решены.

Алиса и Боб играют в очередную игру на массиве $$$a$$$ длины $$$n$$$. Алиса начинает с пустого массива $$$c$$$. Оба игрока ходят по очереди, причем Алиса начинает первой.

В свой ход Алиса выбирает один элемент из $$$a$$$, добавляет его в $$$c$$$, а затем удаляет из $$$a$$$.

В свой ход Боб выбирает не более $$$k$$$ элементов из $$$a$$$, а затем удаляет их из $$$a$$$.

Игра заканчивается, когда массив $$$a$$$ становится пустым. Счет Алисы определяется как MEX$$$^\dagger$$$ элементов $$$c$$$. Алиса хочет максимизировать свой счет, а Боб — минимизировать его. Найдите итоговый счет Алисы, если оба игрока играют оптимально.

Массив будет дан в сжатом формате. Вместо того, чтобы давать элементы, присутствующие в массиве, мы будем давать их частоты. Формально, вам будет дано $$$m$$$ — максимальный элемент массива, а затем $$$m + 1$$$ целых чисел $$$f_0, f_1, \ldots, f_m$$$, где $$$f_i$$$ представляет собой количество раз, которое $$$i$$$ встречается в массиве $$$a$$$.

$$$^\dagger$$$ $$$\operatorname{MEX}$$$ (minimum excludant) массива целых чисел определяется как наименьшее целое неотрицательное число, которое не встречается в массиве. Например:

  • MEX массива $$$[2,2,1]$$$ равен $$$0$$$, потому что $$$0$$$ не принадлежит массиву.
  • MEX массива $$$[3,1,0,1]$$$ равен $$$2$$$, потому что $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ — нет.
  • MEX массива $$$[0,3,1,2]$$$ равен $$$4$$$, потому что $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ — нет.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 500$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$m$$$ и $$$k$$$ ($$$1 \le m \le 50, 1 \le k \le 10^9$$$).

Вторая строка содержит $$$m + 1$$$ целых чисел $$$f_0, f_1, \ldots, f_m$$$ ($$$1 \le f_i \le 10^9$$$).

Гарантируется, что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$1000$$$.

Выходные данные

Для каждого набора входных данных найдите счет Алисы, если оба игрока играют оптимально.

Пример
Входные данные
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
Выходные данные
2
1
3
2
1
Примечание

В первом наборе входных данных массив $$$a$$$ равняется $$$[0, 0, 0, 0, 1, 1, 1, 1, 1]$$$. Возможная игра со счетом $$$2$$$ выглядит следующим образом:

  1. Алиса выбирает элемент $$$0$$$. После этого хода $$$a = [0, 0, 0, 1, 1, 1, 1, 1]$$$ и $$$c=[0]$$$.
  2. Боб выбирает для удаления $$$3$$$ элемента $$$0$$$, $$$0$$$ и $$$1$$$. После этого хода $$$a = [0, 1, 1, 1, 1]$$$ и $$$c=[0]$$$.
  3. Алиса выбирает элемент $$$1$$$. После этого хода $$$a = [0,1,1,1]$$$ и $$$c=[0,1]$$$.
  4. Боб удаляет оставшиеся $$$4$$$ элемента $$$0$$$, $$$1$$$, $$$1$$$ и $$$1$$$. После этого хода $$$a=[\,]$$$ и $$$c=[0,1]$$$.

В конце массив $$$c=[0,1]$$$, его MEX равен $$$2$$$. Обратите внимание, что это пример игры и не обязательно представляет собой оптимальную стратегию для обоих игроков.

Во втором наборе входных данных Алиса может выбрать $$$0$$$ в свой первый ход, гарантируя, что ее счет будет не меньше $$$1$$$. Боб может удалить все копии элемента $$$1$$$ в свой первый ход, гарантируя тем самым, что счет Алисы не будет превосходить $$$1$$$. Таким образом, счет Алисы равен $$$1$$$, если оба игрока играют оптимально.