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