Приближается лунный новый год, поэтому Боб собирается получать красные конверты с огромными деньгами! К сожалению, даже просто забрать деньги из конверта — трудоемкая задача.
Опишем задачу математически. Рассмотрим ось времени с момента \(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\) (включительно), что приведет к тому, что он может пропустить некоторые красные конверты.
Вычислите минимально возможное число монет, которое соберет Боб, если Алиса будет отвлекать его оптимально.
Выходные данные
Выведите одно целое число — минимальное число монет, которое соберет Боб, если Алиса будет отвлекать его оптимальным образом.
Примечание
В первом примере Алиса не может отвлекать Боба. Поэтому Боб соберет монеты в красных конвертах в моменты времени \(1\) и \(5\), и в итоге соберет \(13\) монет.
Во втором примере Алиса должна отвлечь Боба в момент времени \(1\). Тогда Боб пропустит первый конверт, соберет второй и после этого ничего не будет делать. Ответ будет равен \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 0 2
1 3 4 5
2 5 5 8
|
13
|
|
2
|
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
|
|
3
|
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
|