CF2161C Loyalty

你是一家商店的顾客，想要购买 $n$ 件商品。每件商品 $i$ 的价格为 $a_i$，其中 $1 \leq a_i \leq X$，$X$ 是忠诚度因子。 你在商店的忠诚度等级被定义为 $\lfloor \dfrac{S}{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$ 个整数——表示最佳购买顺序下的商品价格。 如果有多种顺序都能获得最大奖励点数，可以输出其中任意一种。

在第一个测试用例中： 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$ 个奖励点数。 由 ChatGPT 5 翻译