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