Canvas Painting

Time limit1sMemory limit256 MB

Summary

Arrange the canvases in a line and repeatedly split one color group into two so every canvas ends with its own color at the smallest total repaint cost.

Level: Medium5 of 10
Topics: Greedy, Heap
Solved: No attempts yet

Problem

After last year's success, Samuel W. E. R. Craft is better known than ever, and he now has the money for every project that comes to mind. His newest one is a row of canvases painted so that no color repeats.

Samuel bought a set of white canvases of varying sizes. Painting them by hand would take far too long, so he built a large machine that does the painting for him. The machine works like this.

Place all canvases in a line on the machine's conveyor belt, in any order you choose.
Pick a color $C$ and a number $F$ smaller than the number of canvases that currently have color $C$ .
Going from left to right, repaint every canvas of color $C$ . The first $F$ of them get a new color $X$ , and the rest get a new color $Y$ . The machine picks $X$ and $Y$ ; they differ from each other and from every color used before. The ink spent in this step equals the sum of the sizes of the repainted canvases.
Repeat steps 2 and 3 until every canvas has a different color.

Suppose Samuel bought four canvases of sizes 3, 5, 5 and 7. The picture below shows two ways of painting them.

Two ways of painting the canvases

Given the sizes of the canvases Samuel bought, find the smallest amount of ink the machine has to spend so that every canvas ends up with a different color.

Input

The first line contains one integer $T$ , the number of test cases. Each test case takes two lines. The first line contains one integer $N$ , the number of canvases. The second line contains $N$ space separated integers, the sizes of the canvases.

Output

Print $T$ lines, one per test case: the smallest amount of ink the machine needs so that every canvas has a different color.

Constraints

$1 \le T \le 100$ , the number of test cases.
$1 \le N_i \le 100000$ , the number of canvases in the $i$ -th test case.
$1 \le s \le 100000$ , the size of each canvas.
$1 \le \sum_{i=1}^{T} N_i \le 100000$ , the number of canvases over all test cases in one input file.

Examples3

Example 1
Input
```
2
3
7 4 7
4
5 3 7 5
```
Expected output
```
29
40
```
Example 2
Input
```
1
1
1
```
Expected output
```
0
```
Example 3
Input
```
1
2
100000 100000
```
Expected output
```
200000
```