Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача C регионального тура. Трамвай

Автор задачи: Региональный этап Всероссийской олимпиады школьников по информатике 2008 / 2009 учебного года

Задачу добавил: alef

Успешно сдано решений: 4

Время на тест - 5 с
Максимальный объем используемой памяти - 64 Мб

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

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

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

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

Формат входных данных

Первая строка входного файла содержит разделенные пробелом три целых числа N, M и P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно (1 ≤ NM,  P ≤ 100 000; 2 ≤ P).

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел ai, bi, ci, di:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−106 ≤ ai, bi ≤ 106; 1 ≤ ci < diP).

Формат выходных данных

В выходной файл необходимо вывести одно целое число — максимальное суммарное удовлетворение, которого могут добиться пассажиры.

Пример входных и выходных данных

input.txt

output.txt

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

28

 

Комментарий к примеру

Максимальное суммарное удовлетворение  достигается следующим образом:
·      На первой остановке входят и садятся второй и третий пассажиры;
·      На второй остановке входят первый и четвертый пассажиры, второй уступает место первому;
·      На третьей остановке встают и выходят первый и третий пассажиры, второй и четвертый садятся на их места;
·      На четвертой остановке выходят первый и третий пассажиры.
 

Примечание

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


Сдать задачу

Задать вопрос жюри по этой задаче