Shawarmiada

Time limit: 1 s.
Memory limit: 256 MB

Besides the National Informatics Competition, Riyadh is also hosting this year’s Shawarmiada. Sultan has decided to win this year and claim a huge amount of delicious prizes.

Shawarmiada is a competition where each participant brings \(N\) shawarmas and measures their weights in a specific way:

  • Sultan first measures the total weight of all shawarmas at once and writes the result on the board.
  • Then, he splits the measured shawarmas into two non-empty disjoint groups and measures them. This process of splitting and measuring then repeats for each of the groups.
  • If a measured group consists of only one shawarma, it is not split further; instead, it is set aside and its process ends.
  • The sum of all numbers written on the board represents Sultan’s final score in the competition.

Sultan wants to know how to perform the splits after each measurement so that his score is as large as possible. Since he is very busy, he asked you for help - and in return, he’ll hook you up with some of the best shawarma in Riyadh.

Input

The first line contains a natural number \(T\) (\(1 \leq T \leq 10\)) - the number of test cases. Each test case is given in the following format:

  • The first line contains a natural number \(N\) (\(1 \leq N \leq 10^5\)) - the number of shawarmas Sultan brings.
  • The second line contains \(N\) natural numbers \(A_1,A_2,…,A_N\), where \(A_i\) (\(1 \leq A_i \leq 10^9\))​ represents the weight of the \(i\)-th shawarma in grams, for \(1\leq i \leq N\).

Output

For each test case, output a single natural number - the maximum score Sultan can achieve in that test case.

Scoring

Subtask Additional constraints Points
\(1\) \(T = 1\), \(N \le 20\) \(12\)
\(2\) \(N \le 1000\) \(19\)
\(3\) \(A_1 = A_2 = \ldots = A_N\) \(25\)
\(5\) no additional constraints \(44\)

Examples

Input

1
3
20 20 20

Output

160

Input

1
3
12 7 18

Output

104

Note

Note: The process is recursive: after measuring a group, Sultan repeats the same procedure for that group if it contains more than one shawarma. The process ends only when every group contains exactly one shawarma.

Explanation: Sultan first measures the total weight 20+20+20=60, then splits into two groups.

The first group contains shawarmas with weights 20 and 20, and the second group contains one shawarma of weight 20.

He then measures the first group: 20+20=40, and splits it into two groups, each with one shawarma of weight 20. After measuring the second group, he writes 20 on the board, and that shawarma is set aside. The same happens for the third and fourth groups.

The board now contains: 60,40,20,20,20, and their sum is 160.

Solution

Think about the process in reverse. Initially, every shawarma is a separate group. Combining two groups of total weights \(x\) and \(y\) creates their parent group and adds \(x+y\) to the score.

To maximize the total, repeatedly combine the two heaviest groups. Their weights are then included again in as many later measurements as possible. Use a max-priority queue.

The individual shawarmas are also measured, so initialize the answer with their total weight. The complexity is \(O(N\log N)\) per test case.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tests;
    cin >> tests;

    while (tests--) {
        int n;
        cin >> n;

        priority_queue<long long> groups;
        long long answer = 0;

        for (int i = 0; i < n; i++) {
            long long weight;
            cin >> weight;
            groups.push(weight);
            answer += weight;
        }

        while (groups.size() > 1) {
            long long first = groups.top();
            groups.pop();
            long long second = groups.top();
            groups.pop();

            long long combined = first + second;
            answer += combined;
            groups.push(combined);
        }

        cout << answer << '\n';
    }
}