Вправи Степана
Степан вирішив досягти успіху не тільки в спортивному програмуванні, а й у спорті. На жаль, пройшло вже багато часу з дня його останнього тренування, тому, щоб набрати хорошу форму, доведеться починати з нуля.
Придумати вправи для тренувань виявилося непросто, тому Степан вирішив пошукати ідеї в Інтернеті. Він знайшов сайт, на якому пропонувалася кілька серій тренувальних вправ. Кожна серія тренувань за планом займає N днів. У кожен з цих N днів пропонується робити одну «вправу дня», а також до нього додаються рекомендації щодо виконання у вигляді "A_i - B_i". Це позначає, що для підвищення рівня сили потрібно виконувати вправу від A_i до B_i раз. Якщо виконувати вправу менш, ніж A_i, або більш, ніж B_i раз, то це принесе скоріш за шкоду, ніж користь. Степан не хоче завдавати собі шкоди, тому буде робити від A_i до B_i раз, або зовсім не робити цю вправу.
Почитавши всі описи вправ, Степан зрозумів, що цей курс не розрахований на новачків, але вирішив не здаватися і адаптувати курс вправ під себе. Він знає, що при вивченні i-ї вправи йому доведеться втратити K_i рівнів сили, зате за виконання вправи X раз його рівень сили зросте на F_i*X. Степан не може вивчити і виконати вправу, якщо його поточний рівень сили менший за K_i. У дні, коли Степану не вистачає сил або часу тренуватись, він може пропускати тренування, і рівень його сили залишається без зміни. Знаючи свої можливості, Степан розуміє, що якщо в якийсь день він виконає вправу більш T разів, то наступні D днів він буде занадто втомленим, щоб займатися.
Якщо Степан виконає вправу більш T разів в якийсь з останніх T днів серії тренувань, то він почне відпочивати з наступного дня, а закінчить вже після кінця серії.Степан хоче отримати від занять максимум користі, тому він планує витратити на них N днів! Для кожної серії тренувань допоможіть йому визначити максимальної рівень сили, який він зможе досягти в кінці тренувань. До початку тренувань рівень сили Афанасія дорівнює нулю.
Формат вхідних даних: Перший рядок вхідного файлу містить єдине ціле число N (1 ≤ N ≤ 10^5) - кількість днів тренувань.
Другий рядок містить два цілих числа T, D (1 ≤ T ≤ 10^6, 1 ≤ D ≤ 10^5), якщо в якийсь день Степан виконає вправу більш T разів, то йому доведеться відпочивати D наступних днів.Наступні N рядків описують вправи, i+2-ий рядок містить опис вправи в день i. Кожна вправа описується числами A_i, B_i, K_i, F_i, (0 ≤ K_i ≤ 10^9, 1 ≤ A_i ≤ B_i ≤ 10^6, 1 ≤ F_i ≤ 10^6), розділеними одиночними пробілами, - де A_i, B_i відповідно рекомендований мінімум і максимум кількості разів виконання вправи, K_i-кількість втрачаються рівнів сили при вивченні вправи, F_i- кількість рівнів сили, одержуваних за кожен раз виконання вправи.
Формат вихідних даних: Перший рядок вихідного файлу має містити одне ціле число S - максимальний рівень сили, який Степан може досягти до кінця тренувань.Наступний рядок повинен містити N цілих чисел X_i - кількість разів виконання вправи в день і, якщо в і-ий день він відпочивав, то виведіть 0.
Пояснення до прикладів:
Щоб досягти максимального рівня сили, треба в перший день виконувати вправу 4 рази, щоб не довелося пропускати наступний день. У другий день Афанасій зможе збільшити свій рівень ще на 790 (втрачає 10 рівнів при вивченні та виконує вправу 8 разів), але тоді він не зможе займатися 1 день (третій день).
У четвертий день він збільшує свій рівень на 48, так як Степан виконав вправу більше 4 разів, він змушений пропустити п'ятий.