C. Сделайте это красивым
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Определим $$$\text{красоту}$$$ числа $$$x$$$ как количество битов, равных $$$1$$$, в его двоичном представлении. Определим красоту массива как сумму красот чисел, которые он содержит.

За одну операцию вы можете выбрать индекс $$$i$$$ $$$(1 \le i \le n)$$$ и увеличить $$$a_i$$$ на $$$1$$$.

Найдите максимальную красоту массива после выполнения не более $$$k$$$ операций.

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

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

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 5000$$$, $$$0 \le k \le 10^{18}$$$) — длина массива и максимальное количество операций.

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

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

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

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

Пример
Входные данные
5
5 2
0 1 7 2 4
5 3
0 1 7 2 4
1 1
3
3 0
2 0 3
1 100000000000
0
Выходные данные
8
9
2
3
36
Примечание

В первом наборе входных данных $$$a = [0, 1, 7, 2, 4]$$$. Можно действовать так:

  • применить первую операцию с $$$i = 1$$$, новый массив будет $$$a = [1, 1, 7, 2, 4]$$$
  • применить вторую операцию с $$$i = 4$$$, новый массив будет $$$a = [1, 1, 7, 3, 4]$$$
Красота этого массива равна $$$1 + 1 + 3 + 2 + 1 = 8$$$. Существуют и другие допустимые решения с той же красотой, например $$$[0, 1, 7, 3, 5]$$$.

В третьем наборе входных данных $$$a = [3]$$$. Поскольку вам не требуется использовать ровно $$$k$$$ операций, оптимально не выполнять ни одной.