[Solution] Price Maximization Codeforces Solution

[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$n$ goods (n$n$ — an even number) is brought to the store, i$i$-th of which has weight ai$a_i$. Before selling the goods, they must be packed into packages. After packing, the following will be done:

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

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

Solution Click Below:-  CLICK HERE

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

Price Maximization Codeforces Solution 

For example, let n=6,k=3$n=6,k=3$, weights of goods a=[3,2,7,1,4,8]$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 a3+a6=7+8=15$a_3+a_6=7+8=15$. The cost of the package will be ⌊153⌋=5$\lfloor \frac{15}{3}\rfloor =5$ burles.
• In the second package put the first and fifth goods, the weight is a1+a5=3+4=7$a_1+a_5=3+4=7$. The cost of the package is ⌊73⌋=2$\lfloor \frac{7}{3}\rfloor =2$ burles.
• In the third package put the second and fourth goods, the weight is a2+a4=2+1=3$a_2+a_4=2+1=3$. The cost of the package is ⌊33⌋=1$\lfloor \frac{3}{3}\rfloor =1$ burle.

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

Input

The first line of the input contains an integer t$t$ (1≤t≤104$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$n$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$) and k$k$ (1≤k≤1000$1\le k\le 1000$). The number n$n$ — is even.

The second line of each test case contains exactly n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai≤109$0\le a_i\le {10}^9$).

It is guaranteed that the sum of n$n$ over all the test cases does not exceed 2⋅105$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.