← 返回题目列表

Codeforces · 1690/E

E. 价格最大化

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

一批 $$$n$$$ 商品($$$n$$$ — 偶数)被带到商店,其中 $$$i$$$ 的重量为 $$$a_i$$$。在出售货物之前,必须将其包装成包裹。打包后,将进行以下操作:

- 将会有$$$\frac{n}{2}$$$包裹,每个包裹恰好包含两件货物;
- 包含索引为 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$) 的货物的包裹重量为 $$$a_i + a_j$$$。

这样,一包重量 $$$x$$$ 的成本始终为 $$$\left \lfloor\frac{x}{k}\right\rfloor$$$ burles(向下舍入),其中 $$$k$$$ — 一个固定的给定值。

将货物包装到包裹中,以使销售收入最大化。换句话说,制作这样的 $$$\frac{n}{2}$$$ 给定货物对,使得值 $$$\left \lfloor\frac{x_i}{k} \right \rfloor$$$ 的总和最大,其中 $$$x_i$$$ 是包裹编号 $$$i$$$ ($$$1 \le i \le \frac{n}{2}$$$) 的重量。

例如,设$$$n = 6,k = 3$$$,货物重量$$$a = [3, 2, 7, 1, 4, 8]$$$。让我们将它们打包到以下包中。

- 在第一个包裹中,我们将放置第三个和第六个货物。它的权重将为$$$a_3 + a_6 = 7 + 8 = 15$$$。包裹的成本为 $$$\left \lfloor\frac{15}{3}\right\rfloor = 5$$$ burles。
- 在第二个包裹中放入第一个和第五个货物,重量为$$$a_1 + a_5 = 3 + 4 = 7$$$。包裹的成本为 $$$\left \lfloor\frac{7}{3}\right\rfloor = 2$$$ burles。
- 第三个包裹中放入第二个和第四个货物,重量为$$$a_2 + a_4 = 2 + 1 = 3$$$。包裹的成本为 $$$\left \lfloor\frac{3}{3}\right\rfloor = 1$$$ burle。

采用这种包装,所有包装的总成本将为 $$$5 + 2 + 1 = 8$$$ burles。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试中的测试用例数量。

测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ ($$$2 \le n \le 2\cdot10^5$$$) 和 $$$k$$$ ($$$1 \le k \le 1000$$$)。数字 $$$n$$$ — 是偶数。

每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$)。

保证所有测试用例的$$$n$$$总和不超过$$$2\cdot10^5$$$。

输出

对于每个测试用例,在单独的行上打印一个数字 - 所有包裹的最大可能总成本。

示例

输入 #1

6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2

输出 #1

8
4
0
2
1
5

注意

语句中分析了第一个测试用例。

在第二个测试用例中,如果将第一个和第二个商品放入第一个包裹中,将第三个和第四个商品放入第二个包裹中,则可以获得等于 $$$4$$$ 的总价值。

在第三个测试用例中,每个项目的成本为 $$$0$$$,因此总成本也将为 $$$0$$$。