Training Site

Skill Issue

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds

You have $N$ skill points. The $i$-th skill point has a value of $v_i$, and can be used to either increase your attack by $v_i$ points, or increase your accuracy by $v_i$ percentage points.

Your average attack damage can be calculated by multiplying your attack by your accuracy – for example, with 40 attack and 50% accuracy, you would deal an average of $40 \times 0.5 = 20$ damage per attack.

Initially, you have 0 attack and 0% accuracy. Note that your accuracy is capped at 100%, but you are allowed to assign a skill point that would otherwise take you above 100% accuracy.

Please find the maximum average attack damage possible by assigning the skill points optimally.

Input

The first line contains a single integer, $N$, the number of skill points.

The second line contains $N$ space-separated integers, $v_1, v_2, \dots, v_N$, the values of each skill point.

Output

You should output a single integer – the maximum average attack damage multiplied by 100.

Constraints

• $1 \le N \le 1000$
• $1 \le v_i \le 100$

• Subtask 1 (20%): All skill points have the same value.
• Subtask 2 (30%): $v_i = i$ for all $i$ ($1 \le i \le N$)
• Subtask 3 (20%): $N \le 16$
• Subtask 4 (30%): No further constraints apply.

Sample Explanation

In the first sample case, you should assign two skill points to attack, and two skill points to accuracy. This results in 120 attack and 120% accuracy (which gets capped to 100%), so the average attack damage multiplied by 100 is $120 \times 100 = 12000$.

In the second sample case, one optimal solution is to assign skill points 1, 2, and 5 to attack, and skill points 3 and 4 to accuracy. This results in 8 attack and 7% accuracy, which gives $8 \times 7 = 56$.

• Sample Input 1

4
60 60 60 60


Sample Output 1

12000

• Sample Input 2

5
1 2 3 4 5


Sample Output 2

56

• Sample Input 3

3
20 30 40


Sample Output 3

2000