Трамвай
С окраины в центр города каждое утро по одному маршруту едут в трамвае 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).
Выходные данные
Вывести максимальное суммарное удовлетворение, которого могут добиться пассажиры.
Комментарий к примеру
Максимальное суммарное удовлетворение достигается следующим образом:
На первой остановке входят и садятся второй и третий пассажиры;
На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
На четвертой остановке выходят первый и третий пассажиры.