Машинні роботи
Ви є директором компанії 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.
Дотримуйтесь формату зразка виводу.