E. Опустошение массива
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны массив $$$a$$$ длины $$$n$$$ и целое число $$$k$$$.

За одну операцию выберите любой элемент $$$x$$$ массива.

  • Если $$$x \le k$$$, удалите $$$x$$$ из массива.
  • Иначе удалите $$$x$$$ и добавьте два элемента, равных $$$\left\lceil \dfrac{x}{2} \right\rceil$$$.

В обоих случаях после выполнения операции увеличьте $$$k$$$ на $$$1$$$.

Найдите минимальное количество операций, необходимое, чтобы сделать массив пустым.

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

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

В первой строке каждого набора входных данных находятся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le n$$$) — длина массива и начальное значение $$$k$$$.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — элементы массива.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
8
4 0
4 4 1 4
3 0
3 2 2
6 3
6 3 6 4 6 5
6 2
6 6 5 6 6 6
5 0
3 5 3 1 3
6 1
6 4 6 5 4 6
7 1
7 2 7 7 3 7 7
8 0
8 8 2 8 8 1 8 8
Выходные данные
6
5
6
8
7
8
11
12
Примечание

В первом примере изначально $$$k = 0$$$. Можно выполнить следующие операции:

  1. Разобьём элемент, равный $$$4$$$, на два элемента, равных $$$2$$$; $$$k$$$ станет равным $$$1$$$.
  2. Удалим элемент, равный $$$1$$$; $$$k$$$ станет равным $$$2$$$.
  3. Удалим элемент, равный $$$2$$$; $$$k$$$ станет равным $$$3$$$.
  4. Удалим элемент, равный $$$2$$$; $$$k$$$ станет равным $$$4$$$.
  5. Удалим элемент, равный $$$4$$$; $$$k$$$ станет равным $$$5$$$.
  6. Удалим элемент, равный $$$4$$$; $$$k$$$ станет равным $$$6$$$.
Массив станет пустым после $$$6$$$ операций.

В четвёртом примере изначально $$$k = 2$$$. Можно выполнить следующие операции:

  1. Разобьём элемент, равный $$$6$$$, на два элемента, равных $$$3$$$; $$$k$$$ станет равным $$$3$$$.
  2. Удалим элемент, равный $$$3$$$; $$$k$$$ станет равным $$$4$$$.
  3. Удалим элемент, равный $$$3$$$; $$$k$$$ станет равным $$$5$$$.
  4. Удалим элемент, равный $$$5$$$; $$$k$$$ станет равным $$$6$$$.
  5. Удалим элемент, равный $$$6$$$; $$$k$$$ станет равным $$$7$$$.
  6. Удалим элемент, равный $$$6$$$; $$$k$$$ станет равным $$$8$$$.
  7. Удалим элемент, равный $$$6$$$; $$$k$$$ станет равным $$$9$$$.
  8. Удалим элемент, равный $$$6$$$; $$$k$$$ станет равным $$$10$$$.
Массив станет пустым после $$$8$$$ операций.