Олимпиадная задачка

E. Упражнения Степана
Time limit: 1000 ms
Memory limit: 128 M
Степан решил достичь успеха не только в программирование, но и в спорте. К сожалению, он очень дано не тренировался, поэтому придется начинать всё с нуля.
Придумать упражнения для тренировок, оказалось не просто, поэтому Степан решил поискать их в интернете. Он нашел сайт на котором предлагается несколько серий тренировочных упражнений. Каждая серия занимает N дней. В каждый из этих N дней предлагается делать одно «упражнение дня», а также к нему предлагаются рекомендации в виде «A_i - B_i». Это означает что для повышения уровня сил нужно выполнить упражнение от A_i до B_i раз. Если не выполнять это условия то это будет вредить, по этому Степан будет делать только от Ai до Bi , или вовсе не делать это упражнение.
Почитав описание упражнений, Степан понял, этот курс не рассчитан на новичков, но решил не сдаваться и подстроить этот курс под себя. Он знает, что при изучение i-го упражнения ему придется потерять К_і уровней силы и при этом за выполнение упражнения Х раз, его уровень вырастет на Fi*X. Степан не может выполнить упражнение, если его текущий запас сил <K_i. В те дни, когда Степану не хватает сил или времени на тренировку он пропустит его, и уровень сил останется без изменений. Зная свои возможности, Степан понимает, если он в какой то день выполнит упражнение больше Т раз, то следующие D дней он будет истощен и ему будет не до спорта.
Если Степан выполнит упражнение больше Т раз в какой-то из последних Т дней серий тренировок, он начнет отдыхать на следующий день, а закончит уже после конца серии. Степан хочет набрать максимум пользы от занятий, поэтому он планирует потратить на них N дней! Для каждой серии тренировок помогите ему узнать максимальный уровень силы, который он сможет достичь в конце тренировок. До начала тренировок запас сил Степана равен 0.

Вход:
Первый рядок N (1 ≤ N ≤ 10^5) количество дней тренировок.
Второй – два целых числа T, D (1 ≤ T ≤ 10^6, 1 ≤ D ≤ 10^5), если в какой-то день Степан выполнит упражнение больше Т раз то будет отдыхать следующие 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), разделенными одиночными пробелами, где Ai, Bi соответсвенно рекомендуемый минимум и максимум количество выполнение упражнения. K_i- количество уровней сил которые будут потрачены на упражнение, Fi- количество уровней сил, полученных за каждый раз выполнения упражнения.


Выход:
Первый рядок который идет на выход содержит одно целое число S – максимальный уровень силы, который Степан может достичь до конца тренировок. Следующий рядок должен содержать N целых чисел Xi - количество раз выполнения упражнения в день і, если в день он отдыхал в і-ый, то вывести 0.


exercises.in

5
4 1
3 5 0 10
6 8 10 100
2 8 10 15
5 6 0 8
2 2 1 7

exercises.out
878
4 8 0 6 0