Машинні роботи#2286
Ви директор компанії 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 \leq 10^5), — кількість доларів, із якою компанія розпочинає реорганізацію (C \leq 10^9), і — кількість днів, протягом яких триває реорганізація (D \leq 10^9).
Кожен із наступних рядків описує одну машину для продажу. Кожен рядок містить чотири цілі числа D_i, P_i, R_i і G_i, що відповідно означають день, у який машина продається, ціну у доларах, за яку її можна купити, ціну перепродажу у доларах, а також щоденний прибуток від її експлуатації. Ці числа задовольняють 1 \leq D_i \leq D, 1 \leq R_i < P_i \leq 10^9 та 1 \leq G_i \leq 10^9.
Останній тестовий набір завершується рядком із трьома нулями.
Для кожного тестового набору виведіть номер випадку й найбільшу кількість доларів, яку ACM може мати наприкінці дня D+1.
Дотримуйтесь формату у прикладі виводу.
Приклад 1