eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

Придумати вправи для тренувань виявилося непросто, тому Степан вирішив пошукати ідеї в Інтернеті. Він знайшов сайт, на якому пропонувалася кілька серій тренувальних вправ. Кожна серія тренувань за планом займає 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 разів, він змушений пропустити п'ятий.

Nümunə

Giriş verilənləri #1
5
4 1
3 5 0 10
6 8 10 100
2 8 10 15
5 6 0 8
2 2 1 7
Çıxış verilənləri #1
878
4 8 0 6 0
Mənbə ІІІ етап Всеукраїнської олімпіади 2014 р.