B-station#2835

B-station

0.5 seconds
64 megabytes
Easy

Near Berlandia, after an earthquake, an underwater station was partially flooded. The station consists of levels. For each level, the following information is given: W_i — the initial amount of water in the level, L_i — the maximum amount of water the level can tolerate, and P_i — the cost required by the engineering team to manually unblock the level. When a level is unblocked, all its water flows to the next level. If the water on a level exceeds L_i, the level automatically becomes unblocked. The engineering team wants to unblock the last level while minimizing their expenses. For this, they have hired you.

Input

The first line contains (1 \leq N \leq 15000). The next lines describe the levels. Each line contains W_i, L_i, P_i (0 \leq W_i, L_i, P_i \leq 15000).

Output

Print the numbers of the levels that need to be unblocked.

Examples

Example 1

Loading
Loading