InternDoor

The cheapest way to add them all up

Mediumgreedy · heapRead the input, print the output

Reported in interviews at (where)

You have a pile of whole numbers. In one step you take any two numbers out of the pile and put back their sum, and that step costs the sum. Keep going until one number is left.

For each pile, find the smallest total cost. A pile of one number costs nothing.

Input

The first line holds T, the number of tests. Each test is two lines: n, then the n whole numbers of the pile.

Output

For each test, one line: the smallest total cost for its pile.

Example
Input
3
4
4 3 2 6
1
7
3
5 5 5
Output
29
0
25
  1. 2 + 3 costs 5, then 4 + 5 costs 9, then 6 + 9 costs 15: 5 + 9 + 15 = 29.
  2. There is nothing to combine.
  3. Any two first cost 10, then 10 + 5 costs 15.

Limits

  • 1 <= T <= 100
  • 1 <= n <= 100000
  • the n of all the tests add up to at most 400000
  • 1 <= each number <= 10000

Hints

Hint 1

A number added early is paid for again in every later step it is part of, so the small numbers should be combined first.

Hint 2

Always combine the two smallest numbers in the pile. A min-heap hands them out in O(log n) each.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.