E. Максимизация цен
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В магазин привезли партию из $$$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}$$$ пар из заданных товаров, чтобы сумма величин $$$\left \lfloor\frac{x_i}{k} \right \rfloor$$$, где $$$x_i$$$ — вес упаковки с номером $$$i$$$ ($$$1 \le i \le \frac{n}{2}$$$), была максимальна.

Например, пусть $$$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\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$$$.

Выходные данные

Для каждого набора входных данных в отдельной строке выведите единственное число — максимально возможную суммарную стоимость всех упаковок.

Пример
Входные данные
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$$$.