CF2161C Loyalty

No Loyalty No Royalty (c) You are a customer in a store and want to buy $ n $ items. Each item $ i $ has a price $ a_i $ such that $ 1 \leq a_i \leq X $ , where $ X $ is a loyalty factor. Your loyalty level in the store is defined as $ \lfloor {S \over X} \rfloor $ , where $ S $ is the total cost of items purchased so far. Initially, $ S = 0 $ . If you buy an item with price $ p $ and your loyalty level increases as a result of this purchase, you earn $ p $ bonus points. Your task is to find the maximum number of bonus points you can earn by choosing an optimal order of purchase for the items.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 2 \cdot 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ ( $ 1 \leq n \leq 10^5 $ ) and $ X $ ( $ 1 \leq X \leq 10^9 $ ) — the number of items and the loyalty factor. The second line of each test case contains $ n $ integers $ a_1 $ , $ a_2 $ , $ \ldots $ , $ a_n $ ( $ 1 \leq a_i \leq X $ ) — the prices of the items. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

For each test case, output two lines. The first line should contain a single integer — the maximum number of bonus points that can be earned. The second line should contain $ n $ integers — the prices of the items in an order of purchase that maximizes the number of bonus points. If there are several orders that maximize the number of bonus points, you can output any of them.

In the first test case: 1. After buying the first item $ S = 1 $ , loyalty level is 0; 2. After buying the second item $ S = 3 $ , this increases loyalty level to $ 1 $ and earns $ 2 $ bonus points; 3. After buying the third item $ S = 5 $ , this increases loyalty level to $ 2 $ and earns $ 2 $ bonus points; 4. After buying the fourth item $ S = 7 $ , this increases loyalty level to $ 3 $ and earns $ 2 $ bonus points; 5. After buying the fifth item $ S = 9 $ , this increases loyalty level to $ 4 $ and earns $ 2 $ bonus points; 6. After buying the sixth item $ S = 11 $ , this increases loyalty level to $ 5 $ and earns $ 2 $ bonus points; 7. After buying the seventh item $ S = 12 $ , this increases loyalty level to $ 6 $ and earns $ 1 $ bonus point; 8. After buying the eighth item $ S = 13 $ ; 9. After buying the ninth item $ S = 14 $ , this increases loyalty level to $ 7 $ and earns $ 1 $ bonus point; 10. After buying the tenth item $ S = 15 $ . Overall we got $ 12 $ bonus points. In the second test case: 1. After buying the first four items $ S = 8 $ , loyalty level is 0; 2. After buying the last item $ S = 13 $ , this increases loyalty level to $ 1 $ and earns $ 5 $ bonus points. In the third test case: 1. After buying the first eight items $ S = 20 $ , loyalty level is 0; 2. After buying the ninth item $ S = 30 $ , this increases loyalty level to $ 1 $ and earns $ 10 $ bonus points; 3. After buying the tenth item $ S = 51 $ , this increases loyalty level to $ 2 $ and earns $ 21 $ bonus points; 4. After buying the eleventh item $ S = 73 $ , this increases loyalty level to $ 3 $ and earns $ 22 $ bonus points.