Minimum Cost to Connect Ropes

You are given a set of ropes, each with a positive integer length. Your task is to connect all the ropes into one single rope with minimal total cost.

The cost to connect two ropes of lengths a and b is given by a+b. When two ropes are connected, they form a new rope whose length is a+b. This process is repeated until only one rope remains.

The problem can be formalized as follows: Given rope lengths \(l_1, l_2, \dots, l_N\), we wish to perform a sequence of operations. At each step, let \(a\) and \(b\) be the two smallest available lengths. The cost for a step is \(a+b\) and the new rope has length \(a+b\). The goal is to minimize the total cost, which is the sum of the costs for each connection.

You need to process multiple datasets. Each dataset starts with an integer \(N\) indicating the number of ropes, followed by a line containing \(N\) space-separated integers. The input terminates with a dataset where \(N=0\) (this dataset should not be processed).

inputFormat

The input consists of multiple datasets. For each dataset:

• The first line contains an integer \(N\) (\(N \ge 0\)), the number of ropes.
• If \(N > 0\), the second line contains \(N\) space-separated positive integers representing the lengths of the ropes.

The last dataset is followed by a line containing a single zero, which should not be processed.

Input is read from standard input (stdin).

outputFormat

For each dataset (except the terminating dataset), output one line containing the minimum total cost required to connect the ropes.

Output should be written to standard output (stdout).

## sample

4
4 3 2 6
5
4 2 7 6 9
0

29
62

</p>