Вам дан массив $$$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$$$ операций.
55 20 1 7 2 45 30 1 7 2 41 133 02 0 31 1000000000000
8 9 2 3 36
В первом наборе входных данных $$$a = [0, 1, 7, 2, 4]$$$. Можно действовать так:
В третьем наборе входных данных $$$a = [3]$$$. Поскольку вам не требуется использовать ровно $$$k$$$ операций, оптимально не выполнять ни одной.
| Codeforces Round 1030 (Div. 2) |
|---|
| Закончено |
