CARNIVAL - Complan Carnival

no tags 

Peet is very excited because he is visiting a carnival for the first time in his life! As luck would have it, the carnival he is visiting today happens to be the largest one in the galaxy. It is known throughout the universe for its gigantic and super-fast anti-gravity Ferris wheels.

Peet is looking forward to riding as many rides as he can. Each of the rides cost a certain about of money. He has brought only a limited amount of money. Peet was starting to worry. However, to complicate matters even more, each of the rides have a height requirement: one has to be at least a certain height to be allowed to ride it. Peet is pretty short for his species, and he isn't tall enough to ride most of the rides!

There is still hope. Since he paid attention at his biophysics classes at school, Peet realises that because of centrifugal force, the super-fast anti-gravity ferries wheels will actually increase his height when he rides them! 

The carnival contains N rides. Peet initially has M intergalactic dollars with him and his height is initially H feet. For each ride i (1 <= i <= N), Peet has to pay m[i] intergalactic dollars and his height has to be at least t[i] feet. Peet has calculated that his height would increase by h[i] feet after riding the ith ride. Help him find the maximum number of rides he can ride at the carnival.

Input

The first line contains 3 integers N, M and H.

The next N lines contain 3 integers each. The (i+1)th line contains integers t[i], m[i] and h[i].

Output

Print a single integer - the maximum number of rides Peet can take at the carnival.

Constraints

1 <= N <= 100

0 <= m[i] <= M <= 1000

0 <= t[i], h[i], H <= 10^7

Example

Input:
5 10 1
3 4 5
10 1 3
2 4 0
1 10 7
1 2 2

Output:
3
Explanation:

Peet can take ride 5, spending 2 intergalactic dollars and increasing his height from 1 to 3. Now that he has at least height 3, he can take ride 1. He spends 4 more dollars and his height increases to 8. Finally, he can use the remaining 4 dollars to take ride 3. He cannot take any more rides since he has run out of money. You can check that Peet cannot ride more than 3 rides in this example.


hide comments
Simes: 2022-06-20 22:49:24

What's the answer for this test case?
2 3 1
1 1 1
3 1 1
Can Peet ride the first ride twice to increase his height enough for the second ride? If yes, I assume that only counts as two (distinct) rides in total?


Added by:jack(chakradarraju)
Date:2011-08-12
Time limit:0.204s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Proposed by Anudhyan