← 返回题目列表

Codeforces · 2118/C

C. 让它变得美丽

中文机器翻译题面 查看原题

给定一个由 $$$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$$$ 操作后的最大美感。

示例

输入
复制

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$$$ 操作,因此最好不执行任何操作。