Description

So long coding time make ChaoChao be more nonsense. In order to spend the boring time, ChaoChao plan to practice his cooking stills.

Now, CC wants to make $N$ foods. The $i-th$ food need $a[i]$ unit meat, but CC find that there is only a whole meat and he need to consume energy to cut meat.
Consumption value is equal to the size of the cut meat. For example, there is a 21 units meat, so CC will consume 21 energy to cut it. CC wants to cut meat into $N$ small meat. He wants to know the minimum number of the energy he need.(The size of the meat bought is equal to the sum of $N$ pieces of meat.)

Format

Input

The first line is a number $N (1 \leq N \leq 20000)$ identified the number of small meat.

Then next $N$ lines, each line contains one number $a[i](1 \leq a[i] \leq 50000)$ means $a[i]$ units of the $i-th$ meat.

Output

The minimum number of the energy.

Samples

3
8
5
8

34