E. Лунный новый год и красные конверты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Приближается лунный новый год, поэтому Боб собирается получать красные конверты с огромными деньгами! К сожалению, даже просто забрать деньги из конверта — трудоемкая задача.

Опишем задачу математически. Рассмотрим ось времени с момента $$$1$$$ до момента $$$n$$$. $$$i$$$-й красный конверт будет доступен с момента времени $$$s_i$$$ до $$$t_i$$$ включительно, он будет содержать $$$w_i$$$ монет. Если Боб хочет забрать из $$$i$$$-го конверта монеты, то он может это сделать только в целочисленный момент времени между $$$s_i$$$ и $$$t_i$$$ включительно, а после этого он не сможет собирать монеты из других конвертов до времени $$$d_i$$$ включительно. Выполняется $$$s_i \leq t_i \leq d_i$$$.

Боб жадный, поэтому он жадно собирает монеты: в каждый момент времени $$$x$$$ он собирает монеты из доступного конверта с максимальным количеством монет. Если есть несколько доступных конвертов с одинаковым максимальным количеством монет, Боб выберет конверт, параметр $$$d$$$ которого максимальный. Если все еще есть несколько вариантов, Боб выберет один из них случайным образом.

Все было бы хорошо, но Алиса — дочь Боба — не хочет, чтобы ее отец собрал слишком много монет. Она может отвлечь Боба не более чем $$$m$$$ раз, каждый раз — в один целочисленный момент времени. Если Алиса решает отвлечь Боба в момент времени $$$x$$$, он не сможет ничего делать в момент времени $$$x$$$ и продолжит свою обычную стратегию в момент времени $$$x + 1$$$ (включительно), что приведет к тому, что он может пропустить некоторые красные конверты.

Вычислите минимально возможное число монет, которое соберет Боб, если Алиса будет отвлекать его оптимально.

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$, $$$0 \leq m \leq 200$$$, $$$1 \leq k \leq 10^5$$$) — длину оси времени, количество раз, которое Алиса может отвлечь Боба, и число красных конвертов, соответственно.

Следующие $$$k$$$ строк описывают $$$k$$$ красных конвертов. $$$i$$$-я строка содержит четыре целых числа $$$s_i$$$, $$$t_i$$$, $$$d_i$$$ и $$$w_i$$$ ($$$1 \leq s_i \leq t_i \leq d_i \leq n$$$, $$$1 \leq w_i \leq 10^9$$$) — отрезок времени, когда доступен $$$i$$$-й конверт, время, начиная с которого Боб может продолжить собирать деньги после того, как он соберет конверты из $$$i$$$-го конверта, и количество монет в этом конверте, соответственно.

Выходные данные

Выведите одно целое число — минимальное число монет, которое соберет Боб, если Алиса будет отвлекать его оптимальным образом.

Примеры
Входные данные
5 0 2
1 3 4 5
2 5 5 8
Выходные данные
13
Входные данные
10 1 6
1 1 2 4
2 2 6 2
3 3 3 3
4 4 4 5
5 5 5 7
6 6 6 9
Выходные данные
2
Входные данные
12 2 6
1 5 5 4
4 6 6 2
3 8 8 3
2 9 9 5
6 10 10 7
8 12 12 9
Выходные данные
11
Примечание

В первом примере Алиса не может отвлекать Боба. Поэтому Боб соберет монеты в красных конвертах в моменты времени $$$1$$$ и $$$5$$$, и в итоге соберет $$$13$$$ монет.

Во втором примере Алиса должна отвлечь Боба в момент времени $$$1$$$. Тогда Боб пропустит первый конверт, соберет второй и после этого ничего не будет делать. Ответ будет равен $$$2$$$.