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