jwpassion1 has found several old, unused transportation cards and decided to get them refunded for cash. jwpassion1 has no use for cash except when playing rhythm games that require $500$-won coins. However, the amount to be refunded happened to have a remainder of exactly $490$ when divided by $500$, resulting in $9$ useless coins, which is troublesome. Therefore, jwpassion1 wants to be careful in the future to avoid getting unnecessary coins.

Specifically, transportation cards must be refunded according to the following rules:

• Transportation cards with a balance of $20\,000$ won or more cannot be refunded.
• The refund fee is $500$ won. That is, the refund amount for the $i$-th transportation card is exactly $A_i - 500$ won. If a transportation card has $A_i \leq 500$, it is impossible to refund because it would result in a loss.
• The sum of the refunded amounts must be divisible by $500$.

Given the number of transportation cards jwpassion1 has and the balance of each card, find the maximum total amount that can be refunded.

Input

The first line contains a non-negative integer $N$ representing the number of transportation cards. ($0 \leq N \leq 100\,000$)

Starting from the second line, $N$ lines follow, each containing the balance $A_i$ of the $i$-th transportation card. ($0 \leq A_i \leq 100\,000$; $A_i$ is a multiple of $10$)

If $N$ is $0$, only the first line is provided as input.

Output

Output the maximum total amount that can be refunded.

If no refund is possible, output $0$.

Examples

Input 1

5
1000
520
450
19500
20000

Output 1

19500

Input 2

4
600
1100
850
950

Output 2

1500

Input 3

4
990
990
990
990

Output 3

0

Input 4

0

Output 4

0

Note

jwpassion1 actually possesses $490$ won received from a previous transportation card refund.