148. B-Station

time limit per test: 0.25 sec.
memory limit per test: 4096 KB
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.

Sample test(s)

1000 1000 1
0 1000 2
2 10 100


Author:Andrew V. Lazarev
Resource:Saratov Regional Olympiad, 2002
Date:Spring, 2002

Server time: 2017-09-24 12:40:06Online Contester Team © 2002 - 2016. All rights reserved.