A set of frogs have accidentally fallen to the bottom of
a large pit. Their only means of escaping the pit is to jump
out of it. Each frog
is described by three parameters
where
is its leap capacity,
its weight, and
its height. The
leap capacity specifies how high that frog can jump. If a
frog’s leap capacity is strictly larger than the depth of the
pit, the frog can directly escape the pit. However, these frogs
are altruistic. Rather than selfishly saving themselves and
leaving the frogs with too limited leap capacity behind, they
collectively aim to save as many of them from the pit as
possible.
The frogs realize that if a frog climbs up on the back of frog
before it jumps, the
first frog stands a
better chance of escaping the pit: it can escape if
is strictly
larger than the depth of the pit.
Furthermore, if frog carrying frog on its back climbs up on the back
of frog , the situation
is even better for frog : it can now escape the pit if
is
strictly larger than the depth of the pit.
The frogs can build even higher piles of frogs this way, the
only restriction is that no frog may carry other frogs of
weight in total amounting to its own weight or heavier. Once a
pile has been used to allow a frog to escape, the frogs in the
pile jump back to the bottom of the pit and they can then form
a new pile (possibly consisting of a different set of frogs).
The question is simply how many frogs can escape the pit
assuming they collaborate to maximize this number?
Input
The first line of input contains two integers and (, ), where is the number of frogs and
is the depth of the
pit in µm. Then follow
lines each containing three integers (),
representing a frog with leap capacity µm, weight µg, and height µm. The sum of all frogs’ weights
is at most µg.
Output
Output the maximum number of frogs that can escape the
pit.
| Sample Input 1 |
Sample Output 1 |
3 19
15 5 3
12 4 4
20 10 5
|
3
|
| Sample Input 2 |
Sample Output 2 |
3 19
14 5 3
12 4 4
20 10 5
|
2
|
