terorista

Najveca zgrada u svetskoj prestionici Beonisu ima N spratova. Na svakom spratu se nalazi bazen. Terorista Joca zeli da srusi zgradu, tako sto ce porusiti prvi sprat a samim tim i celu zgradu. Za svaki sprat su poznate sledece informacije:<br><br>
Wi - tezina vode koja se nalazi u bazenu na i-tom spratu na pocetku<br>
Li - tezina vode koju i -ti sprat moze da izdrzi<br>
Ci - cena dinamita potrebnog da se porusi i-ti sprat<br>
Sva voda iz srusenog sprata odlazi na sledeci nici. Ako tezina vode na nekom spratu postane veca od dozvoljene koju moze da izdrzi, pod se rusi i sva voda prelazi nadole. <br><br>
Vas zadatak je da pomognete teroristi Joci da sa sto manje novca srusi prvi sprat. <br><br>
Ulaz: U prvom redu ulaza je prirodan broj N (1<=N<=100000), koji predstavlja broj spratova. U svakom od sledecih N redova nalaze se po tri cela broja Wi, Li, Ci (0<=Wi,Li,Ci<= 2000000000), velicine naznacene u tekstu zadatka za i-ti sprat. Suma svih W[i] i C[i] za (1<=i<=N) ce uvek biti manja od 2000000000 <br><br>
Izlaz: Na standardni izlaz ispisati minimalnu kolicinu novca potrebnu da se banka potopi. Zatim u sledecih nekoliko redova upisati redbe brojeve spratova koje treba srusiti za minimalno resenje, u redosledu rusenja. <br><br>
Primer:
<br><br>
Ulaz: <br>
4<br>
10 50 100<br>
0 100 3<br>100 100 2<br>
10 50 6<br><br>Izlaz<br>5<br>3<br>2







<br><br>Objasnjenje: <br>
Terorista rusi treci, pa drugi sprat sa minimalnom cenom 5. Drugi sprat se ne rusi sam, jer je tezina vodee nakon eksplozije jednaka trecini izdrzljivosti. Kada bi se rusio samo prvi sprat cena bi bila 100, a kada bi se rusio cetvrti cena bi bila 6.