PACK1 - Packing

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


Added by:Nikola P Borisov
Date:2008-10-01
Time limit:0.200s-5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Bulgarian National Olympiad Selection Contest 4 2005

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.