Машинные работы
Вы являетесь директором компании Arbitrarily Complex Machines (сокращенно ACM), которая занимается производством передовых машин с использованием еще более передовых технологий. Ваша старая производственная техника вышла из строя, и теперь вам необходимо приобрести новые машины для компании. Ваша цель — заработать как можно больше денег в период реструктуризации. В это время вы можете покупать, продавать и эксплуатировать машины для получения прибыли, пока они находятся в собственности ACM. Однако из-за ограничений по пространству ACM может владеть не более чем одной машиной одновременно.
В период реструктуризации на продажу будет выставлено несколько машин. Как эксперт на рынке передовых машин, вы уже знаете цену P_i и день доступности D_i для каждой машины M_i. Обратите внимание, что если вы не купите машину M_i в день D_i, она будет куплена кем-то другим и станет недоступной. Разумеется, вы не можете купить машину, если у ACM недостаточно средств для её приобретения.
Если вы покупаете машину M_i в день D_i, ACM может начать её эксплуатацию с дня D_i + 1. Каждый день эксплуатации машины приносит компании прибыль в размере G_i долларов.
Вы можете продать машину в любой день после её покупки, чтобы вернуть часть её стоимости. Каждая машина имеет цену перепродажи R_i, по которой она может быть продана на рынок. Вы не можете эксплуатировать машину в день её продажи, но можете продать её и использовать вырученные средства для покупки новой машины в тот же день.
Как только период реструктуризации заканчивается, ACM продаст любую машину, которой она все еще владеет. Ваша задача — максимизировать количество денег, которое ACM заработает в период реструктуризации.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается с строки, содержащей три положительных целых числа N, C и D. N — это количество машин на продажу (N ≤ 10^5), C — это количество долларов, с которого компания начинает реструктуризацию (C ≤ 10^9), и D — это количество дней, в течение которых длится реструктуризация (D ≤ 10^9).
Каждая из следующих N строк описывает одну машину на продажу. Каждая строка содержит четыре целых числа D_i, P_i, R_i и G_i, обозначающих (соответственно) день, в который машина выставлена на продажу, цену в долларах, по которой она может быть куплена, цену в долларах, по которой она может быть перепродана, и ежедневную прибыль, генерируемую эксплуатацией машины. Эти числа удовлетворяют условиям 1 ≤ D_i ≤ D, 1 ≤ R_i < P_i ≤ 10^9 и 1 ≤ G_i ≤ 10^9.
Последний тестовый случай завершается строкой, содержащей три нуля.
Выходные данные
Для каждого теста выведите его номер и наибольшее количество долларов, которое ACM может иметь в конце дня D+1.
Следуйте формату примера вывода.