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

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

1 секунда

256 мегабайтів

Середня

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

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

Прочитавши всі описи вправ, Степан зрозумів, що цей курс не розрахований на новачків, але вирішив не здаватися і адаптувати курс вправ під себе. Він знає, що при вивченні $i$ -ї вправи йому доведеться втратити $K_{i}$ K_i рівнів сили, зате за виконання вправи $X$ разів його рівень сили зросте на $F_{i} \cdot X$ F_i \cdot X. Степан не може вивчити і виконати вправу, якщо його поточний рівень сили менший за $K_{i}$ K_i. У дні, коли Степану не вистачає сил або часу тренуватися, він може пропускати тренування, і рівень його сили залишиться без зміни. Знаючи свої можливості, Степан розуміє, що якщо в якийсь день він виконає вправу більш ніж $T$ разів, то наступні $D$ днів він буде занадто втомленим, щоб займатися.

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

Вхідні дані

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

Другий рядок містить два цілих числа $T$ та $D$ ( $1 \leq T \leq 1 0^{6}$ 1 \leq T \leq 10^6, $1 \leq D \leq 1 0^{5}$ 1 \leq D \leq 10^5), якщо в якийсь день Степан виконає вправу більше $T$ разів, то йому доведеться відпочивати $D$ наступних днів. Наступні $N$ рядків описують вправи; $i + 2$ i+2-ий рядок містить опис вправи в день $i$ . Кожна вправа описується числами $A_{i}, B_{i}, K_{i}, F_{i}$ A_i, B_i, K_i, F_i ( $0 \leq K_{i} \leq 1 0^{9}$ 0 \leq K_i \leq 10^9, $1 \leq A_{i} \leq B_{i} \leq 1 0^{6}$ 1 \leq A_i \leq B_i \leq 10^6, $1 \leq F_{i} \leq 1 0^{6}$ 1 \leq F_i \leq 10^6), розділеними одиночними пробілами,— де $A_{i}, B_{i}$ A_i, B_i відповідно рекомендований мінімум і максимум кількості разів виконання вправи, $K_{i}$ K_i — кількість втрачених рівнів сили при вивченні вправи, $F_{i}$ F_i— кількість рівнів сили, одержуваних за кожне виконання вправи.

Вихідні дані

Перший рядок вихідного файлу має містити одне ціле число $S$ — максимальний рівень сили, якого Степан може досягти до кінця тренувань. Наступний рядок повинен містити $N$ цілих чисел $X_{i}$ X_i — кількість разів виконання вправи в день $i$ . Якщо в $i$ -ий день він відпочивав, виведіть $0$ .

Приклади

Приклад 1

Примітка

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

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