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

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

1 second
256 megabytes
Medium

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

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

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

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

Input

Перший рядок вхідного файлу містить єдине ціле число (1 \leq N \leq 10^5) — кількість днів тренувань.

Другий рядок містить два цілих числа (1 \leq T \leq 10^6, 1 \leq D \leq 10^5), якщо в якийсь день Степан виконає вправу більш разів, то йому доведеться відпочивати наступних днів.

Наступні рядків описують вправи, i+2-ий рядок містить опис вправи в день . Кожна вправа описується числами A_i, B_i, K_i, F_i, (0 \leq K_i \leq 10^9, 1 \leq A_i \leq B_i \leq 10^6, 1 \leq F_i \leq 10^6), розділеними одиночними пробілами, — де A_i, B_i відповідно рекомендований мінімум і максимум кількості разів виконання вправи, K_i — кількість втрачаються рівнів сили при вивченні вправи, F_i — кількість рівнів сили, одержуваних за кожен раз виконання вправи.

Output

Перший рядок вихідного файлу має містити одне ціле число — максимальний рівень сили, який Степан може досягти до кінця тренувань.

Наступний рядок повинен містити цілих чисел X_i — кількість разів виконання вправи в день , якщо в -ий день він відпочивав, то виведіть 0.

Examples

Example 1

Loading
Loading

Note

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

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