Problem E2. Island cafe ≡

Statement

The young programmer Vasya lives on the island and has a lunch every day in a cafe near his home. As a regular visitor, Vasya wants to participate in the bonus program of this cafe. Before doing this, he wants to assess the benefits that he could have received if he had been using bonuses for the last N days.

On the i-th day, Vasya spent a_i coins for lunch in a cafe. According to the terms of the bonus program, he could either accumulate ⌊ 0.01 ⋅ a_i⌋ of the cost of lunch in the form of bonuses, or pay up to ⌊ 0.5 ⋅ a_i⌋ with the bonuses that he has.

Help Vasya find out what maximum amount of money he could save, using bonuses during those N days.

Input format

The first line contains an integer N  — the number of days.

The second line contains N integers a_i, separated by a space symbol — the number of coins Vasya spent on lunch on the i-th day.

Output format

Output a single integer — the number of coins that Vasya could save using the bonus program.

Constraints

1 ≤ N ≤ 10³

1 ≤ a_i ≤ 10⁴

Sample tests

2
1000 20

10

3
100 1000 1000

11