Merging Crystal Shards

You are given \(N\) crystal shards, each with an associated energy level. Your task is to merge all shards into one while minimizing the total energy cost.

In each step, you select the two shards with the smallest energy levels, merge them into a new shard, and incur a cost equal to the sum of their energies. The new shard’s energy level is also the sum of the two merged shards. This process is repeated until only a single shard remains.

Formally, if the energy levels are \(a_1, a_2, \dots, a_N\), then at each merging step you pick two shards \(x\) and \(y\) (with \(x \le y\)) and replace them with a new shard of energy \(x+y\), with an added cost of \(x+y\). The goal is to minimize the total cost of all merging operations.

inputFormat

The input is given from the standard input (stdin). The first line contains an integer (N) representing the number of crystal shards. The second line contains (N) space-separated integers, where each integer denotes the energy level of a shard.

outputFormat

Output to the standard output (stdout) a single integer, which is the minimal total energy cost required to merge all the shards into one.## sample

4
4 3 2 1

19