一批 $$$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$$$。