In the future the delivery services will be fully automated. A robot will come to your home to pick the boxes and leaves them in the central processing office where boxes for the same address are packed together. There is a machine that can pack two boxes into a one new box containing the privious two. If we want N boxes delivered to a certain city then this machine with N-1 operation will be able to consolidate them into single box.

Each box has its size and a price for packing it equal to this size. The size of the box resulting from the machine packing two boxes together is simply equal to the sum of the two boxes that are packed together. Your goal is to find out the minimum price for packing N boxes into a single one using the packing machine.

Input

On the first line there will be one number N (1 < N < 5000001) – the number of boxes. N lines follow each line with one number representing the size of N-th box. The size will be less then 1 000 000. In 50% of the test cases the size will be less then 4000.

Output

Your program should output a single integer – the minum price that have to be paid for packing the N boxes into a single one using N-1 operations of the machine.

Example

Input:
4
1
1
1
1


Output:
8