The Zerg army is working on mining more minerals. They have found a mineral patch of length $L$. They have a single drone who will mine the minerals.

This drone needs to divide this mineral patch into sections of length $L_1$ through $L_N$. The drone can cut a mineral patch of length $x$ into two mineral patches, one with length $y$ and the other with length $x-y$. It will take the drone $x$ seconds to perform one such cut. It is guaranteed that $\sum _{i=1}^N{L}_i=L$. The patches are unordered.

What is the minimum amount of time it will take this single drone to divide the mineral patch into the desired sections?

Constraints

$1\le N\le 20\cdot {10}^3$

$1\le L_i\le 50\cdot {10}^3$

Input Specification

The first line will contain a single integer $N$.

Each of the next $N$ lines will contain a single integer, $L_i$.

Output Specification

Output the number of seconds it will take for the drone to divide the mineral patch accordingly.

Sample Input

3
8
5
8

Sample Output

34