Help to solve this problem !
Posted: Tue May 10, 2005 1:48 pm
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.
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.