给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。我们将数字 $$$x$$$ 的 $$$\text{beauty}$$$ 定义为其二进制表示形式的 $$$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]$$$。
- 在 $$$i = 1$$$ 处应用第一个操作,新数组为 $$$a = [1, 1, 7, 2, 4]$$$
- 在 $$$i = 4$$$ 处应用第二个操作,新数组为 $$$a = [1, 1, 7, 3, 4]$$$
在第三个测试用例中,$$$a = [3]$$$。由于您不需要精确地使用 $$$k$$$ 操作,因此最好不执行任何操作。