Price Maximization

题意翻译

本题有多组测试数据。 我们有 $n$ 个礼物，而最终我们需要将所有的礼物两两包成 $\frac{n}{2}$ 个包裹。 每一个礼物 $i$ 都有其价值 $a_i$，而含有礼物 $i$ 与礼物 $j$ 的包裹的价值是 $\lfloor \frac{a_i+a_j}{k} \rfloor$。 我们需要找出一个方案来使得所有包裹的价值之和最大，并求出这个最大值。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #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

说明

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 $ .

**价格最大化**

**题意翻译**

本题有多组测试数据。我们有 $ n $ 个礼物，而最终我们需要将所有的礼物两两包成 $ \frac{n}{2} $ 个包裹。每一个礼物 $ i $ 都有其价值 $ a_i $，而含有礼物 $ i $ 与礼物 $ j $ 的包裹的价值是 $ \left\lfloor \frac{a_i+a_j}{k} \right\rfloor $。我们需要找出一个方案来使得所有包裹的价值之和最大，并求出这个最大值。

**题目描述**

一批 $ 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 $ 的值 $ \left\lfloor \frac{x_i}{k} \right\rfloor $ 的总和最大。

例如，设 $ 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 $ 布雷斯。
- 第二个包裹放入第一个和第五个商品，重量是 $ a_1 + a_5 = 3 + 4 = 7 $。包裹的成本是 $ \left\lfloor \frac{7}{3} \right\rfloor = 2 $ 布雷斯。
- 第三个包裹放入第二个和第四个商品，重量是 $ a_2 + a_4 = 2 + 1 = 3 $。包裹的成本是 $ \left\lfloor \frac{3}{3} \right\rfloor = 1 $ 布雷斯。

这样打包，所有包裹的总成本将是 $ 5 + 2 + 1 = 8 $ 布雷斯。

**输入输出格式**

**输入格式**

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

接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $ n $（$ 2 \le n \le 2 \times 10^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 \times 10^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。**价格最大化** **题意翻译** 本题有多组测试数据。我们有 $ n $ 个礼物，而最终我们需要将所有的礼物两两包成 $ \frac{n}{2} $ 个包裹。每一个礼物 $ i $ 都有其价值 $ a_i $，而含有礼物 $ i $ 与礼物 $ j $ 的包裹的价值是 $ \left\lfloor \frac{a_i+a_j}{k} \right\rfloor $。我们需要找出一个方案来使得所有包裹的价值之和最大，并求出这个最大值。 **题目描述** 一批 $ 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 $ 的值 $ \left\lfloor \frac{x_i}{k} \right\rfloor $ 的总和最大。 例如，设 $ 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 $ 布雷斯。 - 第二个包裹放入第一个和第五个商品，重量是 $ a_1 + a_5 = 3 + 4 = 7 $。包裹的成本是 $ \left\lfloor \frac{7}{3} \right\rfloor = 2 $ 布雷斯。 - 第三个包裹放入第二个和第四个商品，重量是 $ a_2 + a_4 = 2 + 1 = 3 $。包裹的成本是 $ \left\lfloor \frac{3}{3} \right\rfloor = 1 $ 布雷斯。 这样打包，所有包裹的总成本将是 $ 5 + 2 + 1 = 8 $ 布雷斯。 **输入输出格式** **输入格式** 输入的第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。 接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $（$ 2 \le n \le 2 \times 10^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 \times 10^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。