CF2139B Cake Collection

Maple wants to bake some cakes for Chocola and Vanilla. One day, she discovers $$$n$$$ magical cake ovens. The $$$i$$$-th oven bakes $$$a\_i$$$ cakes every second. The cakes remain in their respective ovens until they are collected. At the end of each second, she may teleport to any oven (including the one she is currently at) and collect all the cakes that have accumulated in that oven up to that point. Your task is to determine the maximum number of cakes Maple can collect in $$$m$$$ seconds.

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \\le t \\le 1000$$$). The description of the test cases follows. The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \\leq n \\leq 10^5$$$, $$$1\\leq m\\leq 10^8$$$) — the number of magical ovens and the number of seconds during which Maple will collect cakes. The second line of each test case contains $$$n$$$ integers $$$a\_1, a\_2, \\ldots, a\_n$$$ ($$$1 \\leq a\_i \\le 10^5$$$) — the number of cakes the $$$i$$$-th oven bakes every second. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \\cdot 10^5$$$.

For each test case, output a single integer representing the maximum number of cakes Maple can collect in $$$m$$$ seconds.

For the first test case, one optimal solution is as follows: 1. At the end of the first second, the ovens contain $$$1$$$, $$$2$$$, and $$$3$$$ cakes respectively. Maple teleports to oven $$$3$$$ and collects all $$$3$$$ cakes. Oven $$$3$$$ now has $$$0$$$ cakes remaining. 2. At the end of the second second, the ovens contain $$$2$$$, $$$4$$$, and $$$3$$$ cakes respectively. Maple teleports to oven $$$1$$$ and collects all $$$2$$$ cakes. Oven $$$1$$$ now has $$$0$$$ cakes remaining. 3. At the end of the third second, the ovens contain $$$1$$$, $$$6$$$, and $$$6$$$ cakes respectively. Maple teleports to oven $$$2$$$ and collects all $$$6$$$ cakes. Oven $$$2$$$ now has $$$0$$$ cakes remaining. 4. At the end of the fourth second, the ovens contain $$$2$$$, $$$2$$$, and $$$9$$$ cakes respectively. Maple teleports to oven $$$3$$$ and collects all $$$9$$$ cakes. Oven $$$3$$$ now has $$$0$$$ cakes remaining. In total, Maple collects $$$3+2+6+9=20$$$ cakes. For the second test case, one optimal solution is as follows: 1. At the end of the first second, the ovens contain $$$1$$$, $$$2$$$, and $$$3$$$ cakes respectively. Maple teleports to oven $$$2$$$ and collects all $$$2$$$ cakes. Oven $$$2$$$ now has $$$0$$$ cakes remaining. 2. At the end of the second second, the ovens contain $$$2$$$, $$$2$$$, and $$$6$$$ cakes respectively. Maple teleports to oven $$$3$$$ and collects all $$$6$$$ cakes. Oven $$$3$$$ now has $$$0$$$ cakes remaining. In total, Maple collects $$$2+6=8$$$ cakes.