<PREV Problem:
NEXT>
Solved by 357 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Minimizing number of steps

Time limit = 5 seconds

Petya wants to organize programming contest in his institute and he has to pass some consecutive bureaucratic procedures.

At each step Petya get or pay some money.

He may pay 100 coins to skip next bureaucratic procedures or 200 coins to skip next two procedures or k*100 coins to skip next k.

Please, help Petya to minimize number of bureaucratic procedures.

At the beginning Petya has 0 coins. The last and the first procedures should be passed.

He cannot have negative number of coins.

Input The first line contains number N, (1 ≤ N ≤ 1000 ). Next line contains N integer numbers each less than 10000 in absolute value.

Output Output minimal number of procedures Petya should pass through. or output "-1" if it is impossible to pass trough bureaucratic barrier.

Input#1
1
100
Output#1
1
Input#2
1
-20
Output#2
-1
Input#3
4
120 20 20 20
Output#3
3
Input#4
6
30 30 30 30 30 30
Output#4
5


Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 54.162.181.75