CF1690E.Price Maximization

A batch of $n$ goods ($n$ — an even number) is brought to the store, $i$-th of which has weight $a_i$. Before selling the goods, they must be packed into packages. After packing, the following will be done:

• There will be $\frac{n}{2}$ packages, each package contains exactly two goods;
• The weight of the package that contains goods with indices $i$ and $j$ ($1 \le i, j \le n$) is $a_i + a_j$.

With this, the cost of a package of weight $x$ is always $\left \lfloor\frac{x}{k}\right\rfloor$ burles (rounded down), where $k$ — a fixed and given value.

Pack the goods to the packages so that the revenue from their sale is maximized. In other words, make such $\frac{n}{2}$ pairs of given goods that the sum of the values $\left \lfloor\frac{x_i}{k} \right \rfloor$, where $x_i$ is the weight of the package number $i$ ($1 \le i \le \frac{n}{2}$), is maximal.

For example, let $n = 6, k = 3$, weights of goods $a = [3, 2, 7, 1, 4, 8]$. Let's pack them into the following packages.

• In the first package we will put the third and sixth goods. Its weight will be $a_3 + a_6 = 7 + 8 = 15$. The cost of the package will be $\left \lfloor\frac{15}{3}\right\rfloor = 5$ burles.
• In the second package put the first and fifth goods, the weight is $a_1 + a_5 = 3 + 4 = 7$. The cost of the package is $\left \lfloor\frac{7}{3}\right\rfloor = 2$ burles.
• In the third package put the second and fourth goods, the weight is $a_2 + a_4 = 2 + 1 = 3$. The cost of the package is $\left \lfloor\frac{3}{3}\right\rfloor = 1$ burle.

With this packing, the total cost of all packs would be $5 + 2 + 1 = 8$ burles.

一批 $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$ 卢布（向下取整），其中 $k$ 是一个给定的固定值。

请将商品两两配对装盒，使得销售总收益最大化。换言之，请构造 $\frac{n}{2}$ 对给定商品，使得各包装盒重量 $x_i$（$1 \le i \le \frac{n}{2}$）对应的 $\left\lfloor\frac{x_i}{k}\right\rfloor$ 之和最大。

例如，设 $n = 6,\ k = 3$，商品重量为 $a = [3, 2, 7, 1, 4, 8]$。我们可将它们按如下方式装盒：

• 第一个包装盒放入第 3 件和第 6 件商品，其重量为 $a_3 + a_6 = 7 + 8 = 15$，售价为 $\left\lfloor\frac{15}{3}\right\rfloor = 5$ 卢布；
• 第二个包装盒放入第 1 件和第 5 件商品，其重量为 $a_1 + a_5 = 3 + 4 = 7$，售价为 $\left\lfloor\frac{7}{3}\right\rfloor = 2$ 卢布；
• 第三个包装盒放入第 2 件和第 4 件商品，其重量为 $a_2 + a_4 = 2 + 1 = 3$，售价为 $\left\lfloor\frac{3}{3}\right\rfloor = 1$ 卢布。

采用这种装盒方式，所有包装盒的总售价为 $5 + 2 + 1 = 8$ 卢布。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) —the number of test cases in the test.

The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ ($2 \le n \le 2\cdot10^5$) and $k$ ($1 \le k \le 1000$). The number $n$ — is even.

The second line of each test case contains exactly $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all the test cases does not exceed $2\cdot10^5$.

输入的第一行包含一个整数 $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$。

For each test case, print on a separate line a single number — the maximum possible total cost of all the packages.

对于每个测试用例，在单独一行中输出一个整数——所有包裹的总成本的最大可能值。

The first test case is analyzed in the statement.

In the second test case, you can get a total value equal to $4$ if you put the first and second goods in the first package and the third and fourth goods in the second package.

In the third test case, the cost of each item is $0$, so the total cost will also be $0$.

第一个测试用例在题目描述中已进行分析。

在第二个测试用例中，若将第一和第二个物品放入第一个包裹，第三和第四个物品放入第二个包裹，则可获得总价值 $4$。

在第三个测试用例中，每个物品的成本均为 $0$，因此总成本也为 $0$。