З околиці до центру міста щоранку одним маршрутом їдуть у трамваї \(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\)).

Формат вихідних даних

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

Коментар наприклад тестів

Максимальне сумарне достаток досягається так:

• На першій зупинці входять і сідають другий і третій пасажири;
• На другій зупинці входять перший і четвертий пасажири, другий поступається місцем першому;
• На третій зупинці встають і виходять перший і третій пасажири, другий та четвертий сідають на їхні місця;
• На четвертій зупинці виходять другий та четвертий пасажири.

Оцінювання

• Тест 1 - з умови. Оцінюється на 0 балів.
• Тести 2-31 - числа \(M, N, P\) не перевищують 100. Група тестів оцінюється в 60 балів.
• Тести 32-41 - число \(P\) не перевищує 100. Група тестів оцінюється в 20 балів .
• Тести 42-51 - додаткових обмежень немає. Група тестів оцінюється в 20 балів

Приклад вхідних даних

4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4

Приклад вихідних даних

28