题目描述

给定一个包含 $n$ 个物品（$n$ 为偶数）的批次，第 $i$ 个物品的重量为 $a_i$。在出售这些物品之前，它们必须被打包成包裹。打包之后，将执行以下操作：

将有 $\frac n2$ 个包裹，每个包裹正好包含两个物品； 包含第 $i$ 和第 $j$ 个物品 $(1≤i,j≤n)$ 的包裹的重量为 $a_i+a_j$。

此时，重量为 $x$ 的包裹的价值是 $⌊\frac xk⌋$ （向下取整），其中 $k$ 是一个固定的给定值。将货物打包，使销售收入最大化。换句话说，使 $\frac n2$ 包物品的价值和最大。即使得 $\sum⌊\frac{x_i}k⌋$ 最大，这里 $x_i$ 是第 $i$ 个包裹的重量 $(1≤i≤\frac n2)$。

例如，令 $n=6，k=3$，物品的重量为 $a=[3,2,7,1,4,8]$。让我们将它们打包成以下包裹。

在第一个包裹中，我们将放置第三个和第六个物品。它的重量将是 $a_3+a_6=7+8=15$。该包裹的成本为 $⌊\frac{15}3⌋=5$个货币单位。 在第二个包裹中，放置第一个和第五个物品，重量为 $a_1+a_5=3+4=7$。该包裹的成本为 $⌊\frac 73⌋=2$ 个货币单位。 在第三个包裹中，放置第二个和第四个物品，重量为 $a_2+a_4=2+1=3$。该包裹的成本为 $⌊\frac 33⌋=1$ 个货币单位。

通过这种打包方式，所有包的总成本将为 $5+2+1=8$ 个货币单位。

输入格式

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

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

每个测试用例的第一行包含两个整数 $n(2≤n≤2⋅10^5)$ 和 $k(1≤k≤1000)$。$n$ 是偶数。

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

保证 $n$ 的总和不超过 $2⋅10^5$。

输出格式

对于每个测试用例，请在单独的一行上输出一个数字——所有包裹的最大可能总价值。

测试样例

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

8
4
0
2
1
5

样例说明

在题目描述中已经解释了第一个测试用例。

对于第二个测试用例，如果你将第一个和第二个物品放入第一个包中，将第三个和第四个物品放入第二个包中，你可以获得总价值为 $4$。

对于第三个测试用例，每个物品的费用都是 $0$，因此总费用也将为 $0$。