Make it beauty

Problem Statement

You are given an array $a$ of $n$ integers. We define the $\text{beauty}$ of a number $x$ to be the number of $1$ bits in its binary representation. We define the beauty of an array to be the sum of beauties of the numbers it contains.

In one operation, you can select an index $i$ $(1 \le i \le n)$ and increase $a_i$ by $1$.

Find the maximum beauty of the array after doing at most $k$ operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 5000$, $0 \le k \le 10^{18}$) — the length of the array and the maximal number of operations.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots a_n$ ($0 \le a_i \le 10^9$) —denoting the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

Output

For each test case, output a single integer, the maximum beauty after at most $k$ operations.

Solving

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


int qpow(int x,int y)
{
    int res = 1;
    while(y>0)
    {
        if(y&1) res = res * x;
        x *= x;
        y >>= 1;
    }
    return res;
}
void solve()
{   
    int n,k;
    cin >> n >> k;
    vector<int> val(n+1,0);
    vector<int> arr(n+1);
    int ans = 0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin >> x;
        arr[i] = x;
        bitset<65> bits(x);
        val[i] = bits.count();
        ans += val[i];
    }  
    {
        // 枚举数位
        for(int i=0;i<=60;i++)
        {	
            // 对于每个数位 看一下是否可以被加上
            for(int j=1;j<=n;j++)
            {
                bitset<65> bits(arr[j]);
                if(bits[i]==0)
                {
                    if(k>=qpow(2,i))
                    {
                        k -= qpow(2,i);
                        ans++;
                    }
                    else
                    {
                        cout << ans << endl;
                        return;
                    }
                }
            }
        }
    }
}  