Length of Bundle Rope

Interview

Time limit2sMemory limit1024 MB

Summary
Given the sizes of n parcels, repeatedly join two bundles at a time and pay the sum of their sizes, finding the total cost that ties everything into one bundle for the least rope.
Level

Medium5 of 10

Topics
Greedy, Heap, Implementation, Sorting
Solved
No attempts yet

Problem

With the growth of online shopping, the logistics industry, tightly connected to shipping goods, has prospered enough to need a large workforce. Alex, a truck driver in this growing industry, was tasked with transporting several parcels scattered around the warehouse to other cities as part of his daily routine.

Under the official safety requirements for trucks on the highway, Alex had to tie all the packages tightly to load the goods safely on his truck. Alex knew that the length of cord needed to bundle the packages on the truck depended on the size of the packages themselves. Also, n packages can all be tied up after n - 1 bundles. Moreover, when bundling goods, Alex could bundle only two packages at a time to avoid scattering them. Since the daily consumption of cord was large and Alex had to pay for it, he wanted to bundle all the goods with the shortest cord.

For example, suppose there are 4 parcels of sizes 8, 5, 14, and 26. If Alex ties the first two together, the rope needed is 13 (8+5 = 13), and the rope needed for the last two packages is 40 (14 + 26 = 40). If Alex then bundles these two bundles, the rope he needs is 53 (13 + 40 = 53). So the total length for the 4 packages is 106 (13 + 40 + 53 = 106). If Alex instead ties the first two (8 + 5 = 13), adds the third (13 + 14 = 27), and then bundles the last item (27 + 26 = 53), he needs only 93 (13 + 27 + 53 = 93) of cord. Now your task is to help Alex find the minimum length of cord needed.

Input

The first line contains an integer T, the number of test cases. Each test case consists of two lines. The first line contains a positive integer n, the number of packages. The second line contains n positive integers separated by spaces, the size of each parcel.

Output

For each test case, output the minimum length of bundle rope required to tie all parcels together on one line.

Constraints

  • 1 ≤ T ≤ 10
  • 1 ≤ n ≤ 1000
  • The size of each parcel is at most 1000.

Examples1

  1. Example 1

    Input
    4
6
2 3 4 4 5 7
5
5 15 40 30 10
10
3 1 5 4 8 2 6 1 1 2
9
3 2 1 6 5 2 6 4 3
    Expected output
    63
205
100
98