Connect the cables

Given n cables with their lengths, you would like to connect all those cables together and obtain one big cable. To connect two cables with lengths x and y, you should pay x + y. After connecting those, the resulting cable has a length of x + y.
What is the minimum amount you would spend on connecting all the cables?

Input

The first line of the input contains a single integer n (1 ≀ n ≀ ) the number of cables.
The next line contains space-separated integers (1 ≀ ≀ ) the lengths of cables.

Output

The program should print the minimum amount you would spend on connecting those cables.

Examples

Input
Output
5 1 2 3 6 2
30

Explanation

  1. Connect 1 and 2 β‡’ pay 3 β‡’ 3 3 6 2
  1. Connect 2 and 3 β‡’ pay 5 β‡’ 5 3 6
  1. Connect 3 and 5 β‡’ pay 8 β‡’ 6 8
  1. Connect 6 and 8 β‡’ pay 14

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue