Оператор
Центр телефонної підтримки клієнтів компанії з продажу комп'ютерів JAG зараз переповнений. Надто багато клієнтів звертаються за підтримкою, і вони постійно телефонують до центру. Тому компанія хоче визначити, скільки операторів потрібно, щоб впоратися з цією ситуацією.
Для спрощення розглянемо наступну симуляцію.
Нехай N — кількість клієнтів. i-й клієнт має ідентифікатор i і описується трьома числами: M_i, L_i та K_i. M_i — це час, необхідний для надання підтримки, L_i — максимальний час очікування, поки оператор відповість на дзвінок, а K_i — інтервал часу від завершення дзвінка до повторного дзвінка. Іншими словами: оператору потрібно M_i одиниць часу, щоб обслужити i-го клієнта. Якщо i-й клієнт не отримує відповіді від операторів протягом L_i одиниць часу, він кладе слухавку. Через K_i одиниць часу після завершення дзвінка він телефонує знову.
Один оператор може обслуговувати лише одного клієнта одночасно. Коли оператор завершує дзвінок, він може негайно відповісти на інший дзвінок. Якщо чекає більше одного клієнта, оператор обере клієнта з найменшим ідентифікатором.
На початку симуляції всі клієнти телефонують до центру підтримки одночасно. Симуляція вважається успішною, якщо оператори можуть завершити обслуговування всіх клієнтів протягом T одиниць часу.
Ваше завдання — визначити мінімальну кількість операторів, необхідних для успішного завершення цієї симуляції.
Вхідні дані
Вхід містить кілька наборів даних. Кожен набір даних має наступний формат:
N T M_1 L_1 K_1 ... M_N L_N K_N
Перша строка набору даних містить два додатні цілі числа, N та T (1 ≤ N ≤ 1000, 1 ≤ T ≤ 1000). N вказує кількість клієнтів у наборі даних, а T вказує обмеження часу симуляції.
Наступні N рядків описують інформацію про клієнтів. i-й рядок містить три цілі числа, M_i, L_i та K_i (1 ≤ M_i ≤ T, 1 ≤ L_i ≤ 1000, 1 ≤ K_i ≤ 1000), що описують інформацію про i-го клієнта. M_i вказує час, необхідний для телефонної підтримки, L_i вказує максимальний час очікування, поки оператор відповість на дзвінок, а K_i вказує інтервал часу від завершення дзвінка до повторного дзвінка.
Кінець вводу позначається рядком, що містить два нулі. Цей рядок не є частиною жодного набору даних і тому не повинен оброблятися.
Вихідні дані
Для кожного набору даних виведіть мінімальну кількість операторів, необхідних для успішного завершення симуляції, в окремому рядку.