Упражнения Степана
Степан решил добиться успеха не только в спортивном программировании, но и в спорте. К сожалению, прошло уже много времени с его последней тренировки, поэтому, чтобы вернуться в форму, ему придется начинать с нуля.
Придумать упражнения для тренировок оказалось непросто, поэтому Степан решил поискать идеи в Интернете. Он нашел сайт, где предлагались различные серии тренировочных упражнений. Каждая серия рассчитана на 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 — количество раз выполнения упражнения в день i, если в i-ый день он отдыхал, то выведите 0.
**Пояснение к примерам:**
Чтобы достичь максимального уровня силы, нужно в первый день выполнять упражнение 4 раза, чтобы не пришлось пропускать следующий день. Во второй день Степан сможет увеличить свой уровень еще на 790 (теряет 10 уровней при изучении и выполняет упражнение 8 раз), но тогда он не сможет заниматься 1 день (третий день).
В четвертый день он увеличивает свой уровень на 48, так как Степан выполнил упражнение больше 4 раз, он вынужден пропустить пятый.