C. Лояльность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
No Loyalty No Royalty (c)

Вы — покупатель в магазине и хотите купить $$$n$$$ товаров. Каждый товар $$$i$$$ имеет цену $$$a_i$$$, такую что $$$1 \leq a_i \leq X$$$, где $$$X$$$ — это фактор лояльности.

Ваш уровень лояльности в магазине определяется как $$$\lfloor {S \over X} \rfloor$$$, где $$$S$$$ — это общая стоимость уже купленных товаров. Изначально $$$S = 0$$$.

Если вы покупаете товар с ценой $$$p$$$ и в результате этой покупки ваш уровень лояльности увеличивается, вы получаете $$$p$$$ бонусных баллов.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ ($$$1 \leq n \leq 10^5$$$) и $$$X$$$ ($$$1 \leq X \leq 10^9$$$) — количество товаров и фактор лояльности.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$1 \leq a_i \leq X$$$) — цены товаров.

Гарантируется, что сумма всех $$$n$$$ по всем наборам данных не превышает $$$10^5$$$.

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

Для каждого набора данных выведите две строки.

В первой строке выведите одно целое число — максимальное количество бонусных баллов, которое можно заработать.

Во второй строке выведите $$$n$$$ целых чисел — цены товаров в порядке их покупки для максимального количества бонусных баллов.

Если существует несколько различных способов, дающих максимальное количество бонусных баллов, можно вывести любой из них.

Пример
Входные данные
7
10 2
1 2 1 2 1 2 1 2 1 2
5 10
2 2 2 2 5
11 23
5 5 22 1 21 2 10 3 1 1 2
1 1
1
1 17
11
3 100
44 32 1
16 100500
42801 73112 95296 68791 42217 21871 29316 84405 24273 42894 63370 53473 57156 61369 80 27290
Выходные данные
12
1 2 2 2 2 2 1 1 1 1
5
2 2 2 2 5
53
1 1 5 2 1 2 5 3 10 21 22
1
1
0
11
0
44 32 1
503499
53473 42894 80 57156 42801 61369 42217 63370 29316 68791 27290 73112 24273 84405 21871 95296
Примечание

В первом примере:

  1. После покупки первого товара $$$S = 1$$$, уровень лояльности равен 0;
  2. После покупки второго товара $$$S = 3$$$, уровень лояльности повышается до $$$1$$$, начисляется $$$2$$$ бонусных балла;
  3. После покупки третьего товара $$$S = 5$$$, уровень лояльности повышается до $$$2$$$, начисляется $$$2$$$ бонусных балла;
  4. После покупки четвёртого товара $$$S = 7$$$, уровень лояльности повышается до $$$3$$$, начисляется $$$2$$$ бонусных балла;
  5. После покупки пятого товара $$$S = 9$$$, уровень лояльности повышается до $$$4$$$, начисляется $$$2$$$ бонусных балла;
  6. После покупки шестого товара $$$S = 11$$$, уровень лояльности повышается до $$$5$$$, начисляется $$$2$$$ бонусных балла;
  7. После покупки седьмого товара $$$S = 12$$$, уровень лояльности повышается до $$$6$$$, начисляется $$$1$$$ бонусный балл;
  8. После покупки восьмого товара $$$S = 13$$$;
  9. После покупки девятого товара $$$S = 14$$$, уровень лояльности повышается до $$$7$$$, начисляется $$$1$$$ бонусный балл;
  10. После покупки десятого товара $$$S = 15$$$.

Итого получено $$$12$$$ бонусных баллов.

Во втором примере:

  1. После покупки первых четырёх товаров $$$S = 8$$$, уровень лояльности равен 0;
  2. После покупки последнего товара $$$S = 13$$$, уровень лояльности повышается до $$$1$$$, начисляется $$$5$$$ бонусных баллов.

В третьем примере:

  1. После покупки первых восьми товаров $$$S = 20$$$, уровень лояльности равен 0;
  2. После покупки девятого товара $$$S = 30$$$, уровень лояльности повышается до $$$1$$$, начисляется $$$10$$$ бонусных баллов;
  3. После покупки десятого товара $$$S = 51$$$, уровень лояльности повышается до $$$2$$$, начисляется $$$21$$$ бонусный балл;
  4. После покупки одиннадцатого товара $$$S = 73$$$, уровень лояльности повышается до $$$3$$$, начисляется $$$22$$$ бонусных балла.