您是一家商店的顾客,想要购买 $$$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$$$ 整数 - 使奖励积分数量最大化的购买顺序中的商品价格。
如果有多个订单可以最大化奖励积分,则可以输出其中任何一个。
示例
输入复制
710 21 2 1 2 1 2 1 2 1 25 102 2 2 2 511 235 5 22 1 21 2 10 3 1 1 21 111 17113 10044 32 116 10050042801 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
注意
在第一个测试用例中:
- 购买第一个商品$$$S = 1$$$后,忠诚度为0;
- 购买第二件商品 $$$S = 3$$$ 后,忠诚度等级将提高至 $$$1$$$ 并获得 $$$2$$$ 奖励积分;
- 购买第三件商品 $$$S = 5$$$ 后,忠诚度等级将提高至 $$$2$$$ 并获得 $$$2$$$ 奖励积分;
- 购买第四件商品 $$$S = 7$$$ 后,忠诚度等级将提高至 $$$3$$$ 并获得 $$$2$$$ 奖励积分;
- 购买第五件商品 $$$S = 9$$$ 后,忠诚度等级将提高至 $$$4$$$ 并获得 $$$2$$$ 奖励积分;
- 购买第六件商品 $$$S = 11$$$ 后,忠诚度等级将提高至 $$$5$$$ 并获得 $$$2$$$ 奖励积分;
- 购买第七件商品 $$$S = 12$$$ 后,忠诚度等级将提高至 $$$6$$$ 并获得 $$$1$$$ 奖励积分;
- 购买第八件物品后 $$$S = 13$$$;
- 购买第九件商品 $$$S = 14$$$ 后,忠诚度等级将提升至 $$$7$$$ 并获得 $$$1$$$ 奖励积分;
- 购买第十件物品后 $$$S = 15$$$。
总的来说,我们获得了 $$$12$$$ 奖励积分。
在第二个测试用例中:
- 购买前四件商品$$$S = 8$$$后,忠诚度为0;
- 购买最后一件商品 $$$S = 13$$$ 后,忠诚度等级将提高至 $$$1$$$ 并获得 $$$5$$$ 奖励积分。
在第三个测试用例中:
- 购买前八件商品$$$S = 20$$$后,忠诚度为0;
- 购买第九件商品 $$$S = 30$$$ 后,忠诚度等级将提高至 $$$1$$$ 并获得 $$$10$$$ 奖励积分;
- 购买第十件商品 $$$S = 51$$$ 后,忠诚度等级将提高至 $$$2$$$ 并获得 $$$21$$$ 奖励积分;
- 购买第十一件商品 $$$S = 73$$$ 后,忠诚度等级将提高至 $$$3$$$ 并获得 $$$22$$$ 奖励积分。