The customer telephone support center of the computer sales company called JAG is now incredibly confused. There are too many customers who request the support, and they call the support center all the time. So, the company wants to figure out how many operators needed to handle this situation. For simplicity, let us focus on the following simple simulation. Let \textbf{N} be a number of customers. The \textbf{i}-th customer has id \textbf{i}, and is described by three numbers, \textbf{M_i}, \textbf{L_i} and \textbf{K_i}. \textbf{M_i} is the time required for phone support, \textbf{L_i} is the maximum stand by time until an operator answers the call, and \textbf{K_i} is the interval time from hanging up to calling back. Let us put these in other words: It takes \textbf{M_i} unit times for an operator to support \textbf{i}-th customer. If the \textbf{i}-th customer is not answered by operators for \textbf{L_i} unit times, he hangs up the call. \textbf{K_i} unit times after hanging up, he calls back. One operator can support only one customer simultaneously. When an operator finish a call, he can immediately answer another call. If there are more than one customer waiting, an operator will choose the customer with the smallest id. At the beginning of the simulation, all customers call the support center at the same time. Thesimulation succeeds if operators can finish answering all customers within \textbf{T} unit times. Your mission is to calculate the minimum number of operators needed to end this simulation successfully. \InputFile The input contains multiple datasets. Each dataset has the following format: \textbf{N T M_1 L_1 K_1 ... M_N L_N K_N} The first line of a dataset contains two positive integers, \textbf{N} and \textbf{T} (\textbf{1} ≤ \textbf{N} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{T} ≤ \textbf{1000}). \textbf{N} indicates the number of customers in the dataset, and \textbf{T} indicates the time limit of the simulation. The following \textbf{N} lines describe the information of customers. The \textbf{i}-th line contains three integers, \textbf{M_i}, \textbf{L_i} and \textbf{K_i} (\textbf{1} ≤ \textbf{M_i} ≤ \textbf{T}, \textbf{1} ≤ \textbf{L_i} ≤ \textbf{1000}, \textbf{1} ≤ \textbf{K_i} ≤ \textbf{1000}), describing \textbf{i}-th customer’s information. \textbf{M_i} indicates the time required for phone support, \textbf{L_i} indicates the maximum stand by time until an operator answers the call, and \textbf{K_i} indicates the is the interval time from hanging up to calling back. The end of input is indicated by a line containing two zeros. This line is not part of any dataset and hence should not be processed. \OutputFile For each dataset, print the minimum number of operators needed to end the simulation successfully in a line.