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