Feed with Candy

2000ms

262144K

Description:

The hero of the Cut the Rope game is a little monster named Om Nom. He loves candies. And what a coincidence! He also is the hero of today's problem.

$\text{[math]}$

One day, Om Nom visited his friend Evan. Evan has n candies of two types (fruit drops and caramel drops), the i-th candy hangs at the height of h_i centimeters above the floor of the house, its mass is m_i. Om Nom wants to eat as many candies as possible. At the beginning Om Nom can make at most x centimeter high jumps. When Om Nom eats a candy of mass y, he gets stronger and the height of his jump increases by y centimeters.

What maximum number of candies can Om Nom eat if he never eats two candies of the same type in a row (Om Nom finds it too boring)?

Input:

The first line contains two integers, n and x (1 ≤ n, x ≤ 2000) — the number of sweets Evan has and the initial height of Om Nom's jump.

Each of the following n lines contains three integers t_i, h_i, m_i (0 ≤ t_i ≤ 1; 1 ≤ h_i, m_i ≤ 2000) — the type, height and the mass of the i-th candy. If number t_i equals 0, then the current candy is a caramel drop, otherwise it is a fruit drop.

Output:

Print a single integer — the maximum number of candies Om Nom can eat.

Sample Input:

Sample Output:

Note:

One of the possible ways to eat 4 candies is to eat them in the order: 1, 5, 3, 2. Let's assume the following scenario:

Initially, the height of Om Nom's jump equals 3. He can reach candies 1 and 2. Let's assume that he eats candy 1. As the mass of this candy equals 4, the height of his jump will rise to 3 + 4 = 7.
Now Om Nom can reach candies 2 and 5. Let's assume that he eats candy 5. Then the height of his jump will be 7 + 5 = 12.
At this moment, Om Nom can reach two candies, 2 and 3. He won't eat candy 2 as its type matches the type of the previously eaten candy. Om Nom eats candy 3, the height of his jump is 12 + 3 = 15.
Om Nom eats candy 2, the height of his jump is 15 + 1 = 16. He cannot reach candy 4.

Informação

Provedor Codeforces

Código CF436A