Задача C. Пассажиры трамвая ≡

Условие

С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.

Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — a_i и b_i. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется a_i, если же он стоит, то прибавляется b_i.

Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них a_i < b_i).

Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины a_i и b_i, а также номера остановок, на которых он садится и выходит из трамвая.

В примере максимум достигается следующим образом: на 1-й остановке входят и садятся второй и третий пассажиры; на 2-й остановке входят первый и четвертый пассажиры, второй уступает место первому; на 3-й остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места; на 4-й остановке выходят второй и четвертый пассажиры.

За прохождение всех тестов с P ≤ 100 решение получит 80 баллов, за прохождение всех тестов с N, M, P ≤ 100 — 60 баллов.

Формат входного файла

Первая строка входного файла содержит три целых числа N M P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно.

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел a_i b_i c_i d_i, где первые два числа определяют вклад в суммарное удовлетворение, третье — номер остановки, на которой пассажир садится в трамвай, и последнее — номер остановки, на которой он выходит из трамвая (1 ≤ c_i < d_i ≤ P).

Формат выходного файла

Ограничения

1 ≤ N, M ≤ 10⁵; 2 ≤ P ≤ 10⁵;  − 10⁶ ≤ a_i, b_i ≤ 10⁶

Примеры тестов

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

28