Under construction

Still being built. Things may change

Operator

Time limit8sMemory limit512 MB

Summary
Simulate callers who retry after hanging up, and find the fewest operators so all calls finish within time T.
Level

Medium7 of 10

Topics
Simulation, Binary search, Implementation, Greedy
Solved
No attempts yet

Problem

The customer telephone support center of the computer sales company JAG is in chaos. Too many customers ask for support, and they call all the time. The company wants to work out how many operators it needs to handle the situation.

To keep things simple, consider only the following simulation.

There are NN customers. Customer ii has id ii and is described by three integers MiM_i, LiL_i, and KiK_i. An operator needs MiM_i unit times to support customer ii. If no operator answers customer ii within LiL_i unit times of the moment that customer places the call, the customer hangs up. KiK_i unit times after hanging up, the customer calls back. If an operator answers at exactly LiL_i unit times after the call was placed, the call connects; if nobody has answered by that moment, the customer hangs up.

One operator supports only one customer at a time. An operator who finishes a call can answer another call immediately. If more than one customer is waiting, the operator picks the customer with the smallest id.

At the start of the simulation every customer calls the support center at the same time. The simulation succeeds if the support of all customers is finished within TT unit times. A call that finishes exactly at TT counts as finished in time.

Compute the minimum number of operators needed for the simulation to succeed.

Input

The input contains multiple datasets. Each dataset has the following format:

N T
M1 L1 K1
.
.
.
MN LN KN

The first line of a dataset contains two positive integers NN and TT (1≤N≤10001 \le N \le 1000, 1≤T≤10001 \le T \le 1000). NN is the number of customers in the dataset, and TT is the time limit of the simulation.

The following NN lines describe the customers. The ii-th of those lines contains three integers MiM_i, LiL_i, and KiK_i (1≤Mi≤T1 \le M_i \le T, 1≤Li≤10001 \le L_i \le 1000, 1≤Ki≤10001 \le K_i \le 1000).

The end of the input is indicated by a line containing two zeros. That line is not part of any dataset, so do not process it.

Output

For each dataset, print the minimum number of operators needed for the simulation to succeed on its own line.

Examples2

  1. Example 1

    Input
    3 300
100 50 150
100 50 150
100 50 150
3 300
100 50 150
100 50 150
200 50 150
9 18
3 1 1
3 1 1
3 1 1
4 100 1
5 100 1
5 100 1
10 5 3
10 5 3
1 7 1000
10 18
1 2 3
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
7 8 9
8 9 10
9 10 11
10 11 12
0 0
    Expected output
    2
3
3
4

  2. Example 2

    Input
    3 6
2 100 1
2 100 1
2 100 1
3 5
2 100 1
2 100 1
2 100 1
0 0
    Expected output
    1
2