## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Price Maximization Codeforces Solution

E. Price Maximization
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $⌊\frac{x}{k}⌋$ 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 $⌊\frac{{x}_{i}}{k}⌋$, 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=\left[3,2,7,1,4,8\right]$. 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 $⌊\frac{15}{3}⌋=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 $⌊\frac{7}{3}⌋=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 $⌊\frac{3}{3}⌋=1$ burle.

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

Input

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\cdot {10}^{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\cdot {10}^{5}$.

Output

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