eolymp
Задачи

Вправи Степана

Вправи Степана

Степан вирішив досягти успіху не тільки в спортивному програмуванні, а й у спорті. На жаль, пройшло вже багато часу з дня його останнього тренування, тому, щоб набрати хорошу форму, доведеться починати з нуля.

Придумати вправи для тренувань виявилося непросто, тому Степан вирішив пошукати ідеї в Інтернеті. Він знайшов сайт, на якому пропонувалася кілька серій тренувальних вправ. Кожна серія тренувань за планом займає N днів. У кожен з цих N днів пропонується робити одну «вправу дня», а також до нього додаються рекомендації щодо виконання у вигляді "Ai - Bi". Це позначає, що для підвищення рівня сили потрібно виконувати вправу від Ai до Bi раз. Якщо виконувати вправу менш, ніж Ai, або більш, ніж Bi раз, то це принесе скоріш за шкоду, ніж користь. Степан не хоче завдавати собі шкоди, тому буде робити від Ai до Bi раз, або зовсім не робити цю вправу.

Почитавши всі описи вправ, Степан зрозумів, що цей курс не розрахований на новачків, але вирішив не здаватися і адаптувати курс вправ під себе. Він знає, що при вивченні i-ї вправи йому доведеться втратити Ki рівнів сили, зате за виконання вправи X раз його рівень сили зросте на Fi*X. Степан не може вивчити і виконати вправу, якщо його поточний рівень сили менший за Ki. У дні, коли Степану не вистачає сил або часу тренуватись, він може пропускати тренування, і рівень його сили залишається без зміни. Знаючи свої можливості, Степан розуміє, що якщо в якийсь день він виконає вправу більш T разів, то наступні D днів він буде занадто втомленим, щоб займатися.

Якщо Степан виконає вправу більш T разів в якийсь з останніх T днів серії тренувань, то він почне відпочивати з наступного дня, а закінчить вже після кінця серії.
Степан хоче отримати від занять максимум користі, тому він планує витратити на них N днів! Для кожної серії тренувань допоможіть йому визначити максимальної рівень сили, який він зможе досягти в кінці тренувань. До початку тренувань рівень сили Афанасія дорівнює нулю.

Формат вхідних даних: Перший рядок вхідного файлу містить єдине ціле число N (1 ≤ N ≤ 105) - кількість днів тренувань.

Другий рядок містить два цілих числа T, D (1 ≤ T ≤ 106, 1 ≤ D ≤ 105), якщо в якийсь день Степан виконає вправу більш T разів, то йому доведеться відпочивати D наступних днів.
Наступні N рядків описують вправи, i+2-ий рядок містить опис вправи в день i. Кожна вправа описується числами Ai, Bi, Ki, Fi, (0 ≤ Ki ≤ 109, 1 ≤ Ai ≤ Bi ≤ 106, 1 ≤ Fi ≤ 106), розділеними одиночними пробілами, - де Ai, Bi відповідно рекомендований мінімум і максимум кількості разів виконання вправи, Ki-кількість втрачаються рівнів сили при вивченні вправи, Fi- кількість рівнів сили, одержуваних за кожен раз виконання вправи.

Формат вихідних даних: Перший рядок вихідного файлу має містити одне ціле число S - максимальний рівень сили, який Степан може досягти до кінця тренувань.
Наступний рядок повинен містити N цілих чисел Xi - кількість разів виконання вправи в день і, якщо в і-ий день він відпочивав, то виведіть 0.

Пояснення до прикладів:

Щоб досягти максимального рівня сили, треба в перший день виконувати вправу 4 рази, щоб не довелося пропускати наступний день. У другий день Афанасій зможе збільшити свій рівень ще на 790 (втрачає 10 рівнів при вивченні та виконує вправу 8 разів), але тоді він не зможе займатися 1 день (третій день).

У четвертий день він збільшує свій рівень на 48, так як Степан виконав вправу більше 4 разів, він змушений пропустити п'ятий.

Лимит времени 1 секунда
Лимит использования памяти 256 MiB
Входные данные #1
5
4 1
3 5 0 10
6 8 10 100
2 8 10 15
5 6 0 8
2 2 1 7
Выходные данные #1
878
4 8 0 6 0
Источник ІІІ етап Всеукраїнської олімпіади 2014 р.