REDARR2 - Reduce the array

Given an array of size n, you need to reduce the array. In one step, remove any two elements from the array and add their sum instead. Continue addition and removal until no further reduction possible. Output the minimum cost of reduction possible for the given array. 

Input

First line contains a positive integer T representing number of testcases.

Next line contains a number n denoting the size of array.

Next line contains N space separated positive integers (A[i])

1 ≤ T ≤ 50

1 ≤ n ≤ 106

1 ≤ A[i] ≤ 106

Output

Output minimum cost of reduction.

Example

Input:
2
4
1 6 3 20
3
2 2 2

Output:
44
10

Explanation:

Example 1:

  • Remove {1,3} and insert 1+3=4, array becomes [4 6 20], cost=1+3=4
  • Next remove {4,6} and insert 4+6=10, array becomes [10 20], cost=4+6=10 and overall cost=4+10=14
  • Next remove {10,20} and insert 10+20=30, array becomes [30], cost=10+20=30 and overall cost=14+30=44
  • Array cannot be reduced further, hence reduction cost is 44. This sequence of reduction also gives the minimum possible cost. You will see all other sequences give greater or equal cost.

Example 2:

  • Remove {2,2} and insert 2+2=4, array becomes [4 2 ], cost=2+2=4
  • Next remove {4,2} and insert 4+2=6, array becomes [6], cost=4+2=6 and overall cost=4+6=10
  • Array cannot be reduced further, hence reduction cost is 10.

Added by:Kriti Joshi
Date:2019-07-22
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-02-06 07:49:29
fun problem :)
2020-12-25 06:57:27
some hint...... <snip>

[NG]: Nobody asked you for one.

Last edit: 2020-12-25 16:45:01
2020-06-24 14:28:50
I'm not gonna spoil you but, whatever logic you use, choose long long instead of int.
2019-09-24 22:16:35
@akshayjhamb2 Send me your code, then I can check it for you.
2019-08-22 13:07:01
Kriti Joshi - could you please see my solution and tell me where am i making mistake?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.