Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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

Subtasks

  • 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