该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

铁板鱼沉迷于酸角洲已经没法自拔了，布洛尼亚兰德 决定给使用自己的钞能力使铁板鱼诸事不顺，但是我们的铁板鱼有属于自己的能力，他能够通过一串魔咒:"比比拉布巴巴博弈我的刀盾"来使自己的运气提升，但是这串咒语会有亿点副作用。。。咒语的执行必须需要铁板鱼去完成任务，身为乐于助人的你，能帮助可怜的铁板鱼夺回他的运气和他失之交臂的非洲之心吗？

题目描述

咒语会给定一个包含 $n$ 个整数的数组 $a$。咒语定义一个数字 $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$ 次操作，最优解是不进行任何操作。