time limit per test: 0.25
memory limit per test: 4096
input: standard input
output: standard output
There is a half-waterlogged underwater station not far from the famous country Berland. The station consists of N levels. The following information is known about each level: Wi - the weigth of water on i-th before the act of terrorism, Li - the weight of water the i-th level can hold, and Pi - amount of money terrorist are required to depressurize i-th level. All the water from the depressurized level pours to the next level. If the weight of the water on i-th level is more then Li, then it becomes depressurized. The terrorists from Pivland want to depressurize the last (N-th) level spending the least amount of money. They hired you to do this.
The first line of input contains the natural number N (1<=N<=15000). Each of the following N lines contains 3 numbers Wi, Li, Pi (0<=Wi,Li,Pi<=15000).
Write to the output the numbers of levels, which must be depressurized.
1000 1000 1
0 1000 2
2 10 100
|Author:||Andrew V. Lazarev
|Resource:||Saratov Regional Olympiad, 2002
|Server time: 2018-06-19 10:35:57||Online Contester Team © 2002 - 2016. All rights reserved.|