Від окраїни до центру міста кажен ранок по одному маршруту їдуть у трамваї \textbf{n }чоловік. За довгий час поїздок вони достатотньо добре взнали оин одного. Щоб нікому не було образливо, вони захотіли вирішити, хто з них і між якими зупинками маршруту повинен сидіти, а хто повинен стояти. Всі зупинки пронумеровані від \textbf{1 }до \textbf{p}\textit{.} Один з пасажирів виявився знавцем теорії математичного моделювання. Він запропонував розглянути значення \textit{сумарного задоволення} пасажирів. Для кожного \textbf{i}-го пасажира він оцінив дві величини --- \textbf{a_i} і \textbf{b_i}. Якщо протягом одного переїзду між зупинками пасажир сидить, то до сумарного задоволення додається \textbf{a_i}, якщо ж він стоїть, то додається \textbf{b_i}. Всього в трамваї \textbf{m }сидячих місць. Вставати і сідити пасажири можуть миттєво на довільній зупинці. Крім того, деякі пасажири віддають перевагу поїздці стоячи, навіть якщо в трамваї є вільні місця (для них \textbf{a_i} < \textbf{b_i}). Напишіть програму, яка обчислює значення максимально досяжного сумарного задоволення, якщо для кожного \textbf{i}-го пасажира відомі величини \textbf{a_i} і \textbf{b_i}, а також номери зупинок, на яких він сідає і виходить з трамвая. \InputFile Перший рядок містить відокремлені пропуском три цілих числа \textbf{n}, \textbf{m} і \textbf{p }(\textbf{1 }≤ \textbf{n}, \textbf{m}, \textbf{p }≤ \textbf{100 000}, \textbf{2 }≤ \textbf{p}) - число пасажирів, число сидячих місць і число зупинок на маршруті відповідно. Кожен з наступних \textbf{n }рядків містить інформацію про чергового пасажирі у вигляді чотирьох цілих чисел \textbf{a_i}, \textbf{b_i}, \textbf{c_i}, \textbf{d_i}:, де перші два числа визначають вклад в параметр щастя, третє -- номер зупинки, на якій пасажир сідає в трамвай, і останнє -- номер зупинки, на якій він виходить з трамвая (-\textbf{10^6} ≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{10^6}, \textbf{1 }≤ \textbf{c_\{i \}}< \textbf{d_\{i \}}≤ \textbf{p}). \OutputFile Вивести максимальне сумарне задоволення, якого можуть добитись пасажири. \textbf{Коментарі до прикладу} Максимальне сумарне задоволенння досягається наступним чином: \begin{itemize} \item На першій зупинці входять і сідають другий і третій пасажири; \item На другій зупинці входять перший і четвертий пасажири, другий поступається місцем першому; \item На третій зупинці встають і виходять перший і третій пасажири, другий і четвертий сідають на їх місця; \item На четвертій зупинці виходять перший і третій пасажири. \end{itemize}