You are given ~N~ files with positive sizes.

You want to merge them into a single file. Each merge operation must choose exactly two files, and the cost of that operation is the sum of their sizes. After merging two files of sizes ~a~ and ~b~, they become one new file of size ~a + b~.

Your task is to find the minimum possible total cost to merge all files into one file.

Input Format

The first line contains a single integer ~N~.

The second line contains ~N~ integers ~s_1, s_2, ..., s_N~, where ~s_i~ is the size of file ~i~.

Output Format

Print a single integer: the minimum total cost.

Example

Input

4
8 4 6 12

Output

58

Explanation

One optimal sequence of merges is:

• merge ~4~ and ~6~, cost ~10~
• merge ~8~ and ~10~, cost ~18~
• merge ~12~ and ~18~, cost ~30~

The total cost is ~10 + 18 + 30 = 58~.

Constraints

• ~1 ≤ N ≤ 200000~
• ~1 ≤ s_i ≤ 10^9~

Notes

• If ~N = 1~, the answer is ~0~ because no merge is needed.
• The result may not fit in a 32-bit integer.

Subtasks

• 50% of the tests satisfy ~N ≤ 5000~.
• 50% of the tests use the full constraints.