A. Центр переработки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В центре переработки есть $$$n$$$ мусорных баков, $$$i$$$-й бак имеет вес $$$a_i$$$. В каждую секунду происходят два действия:

  • Сначала вы должны выбрать мусорный бак и уничтожить его. Это стоит $$$1$$$ монету, если его вес строго больше чем $$$c$$$, и стоит $$$0$$$ монет иначе.
  • После этого вес оставшихся мусорных баков умножается на два.
Каково минимальное количество монет, которое требуется, чтобы избавиться от всех мусорных баков.
Входные данные

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \leq n \leq 30$$$, $$$1 \leq c \leq 10^9)$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — веса мусорных баков.

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

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

Пример
Входные данные
4
5 10
10 4 15 1 8
3 42
1000000000 1000000000 1000000000
10 30
29 25 2 12 15 42 14 6 16 9
10 1000000
1 1 1 1 1 1 1 1 1 864026633
Выходные данные
2
3
6
1
Примечание

В последующих пояснениях:

  • Синими числами обозначены мусорные баки, которые были уничтожены бесплатно.
  • Красными числами обозначены мусорные баки, которые были уничтожены за $$$1$$$ монету.
  • Черными числами обозначены мусорные баки, которые еще не были уничтожены.

В первом наборе входных данных одно из возможных решений:

  • $$$[10, 4, 15, 1, 8]$$$
  • $$$[\color{blue}{10}, 8, 30, 2, 16]$$$, $$$10$$$ уничтожено бесплатно, потому что $$$10 \leq 10$$$.
  • $$$[\color{blue}{10}, \color{blue}{8}, 60, 4, 32]$$$, $$$8$$$ уничтожено бесплатно, потому что $$$8 \leq 10$$$.
  • $$$[\color{blue}{10}, \color{blue}{8}, 120, 8, \color{red}{32}]$$$, $$$32$$$ уничтожено за $$$1$$$ монету, потому что $$$32 \gt 10$$$.
  • $$$[\color{blue}{10}, \color{blue}{8}, 240, \color{blue}{8}, \color{red}{32}]$$$, $$$8$$$ уничтожено бесплатно, потому что $$$8 \leq 10$$$.
  • $$$[\color{blue}{10}, \color{blue}{8}, \color{red}{240}, \color{blue}{8}, \color{red}{32}]$$$, $$$240$$$ уничтожено за $$$1$$$ монету, потому что $$$240 \gt 10$$$.

За суммарную стоимость в $$$2$$$ монеты.

Во втором наборе входных данных одно из возможных решений:

  • $$$[1\,000\,000\,000, 1\,000\,000\,000, 1\,000\,000\,000]$$$
  • $$$[\color{red}{1\,000\,000\,000}, 2\,000\,000\,000, 2\,000\,000\,000]$$$, $$$1\,000\,000\,000$$$ уничтожено за $$$1$$$ монету, потому что $$$1\,000\,000\,000 \gt 42$$$.
  • $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, 4\,000\,000\,000]$$$, $$$2\,000\,000\,000$$$ уничтожено за $$$1$$$ монету, потому что $$$2\,000\,000\,000 \gt 42$$$.
  • $$$[\color{red}{1\,000\,000\,000}, \color{red}{2\,000\,000\,000}, \color{red}{4\,000\,000\,000}]$$$, $$$4\,000\,000\,000$$$ уничтожено за $$$1$$$ монету, потому что $$$4\,000\,000\,000 \gt 42$$$.