No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard input

output: standard output

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.

Input

3

1000 1000 1

0 1000 2

2 10 100

1000 1000 1

0 1000 2

2 10 100

Output

1

2

2

Author: | Andrew V. Lazarev |

Resource: | Saratov Regional Olympiad, 2002 |

Date: | Spring, 2002 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2020 11:57:43 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|