Оператор
Центр телефонной поддержки клиентов компании по продаже компьютеров 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 — интервал до повторного звонка.
Конец ввода обозначается строкой с двумя нулями. Эта строка не является частью данных и не обрабатывается.
Выходные данные
Для каждого набора данных выведите минимальное количество операторов, необходимых для успешного завершения симуляции, в отдельной строке.