D. Илья и дороги
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В городе Ильи все хорошо, кроме дорог, потому что единственная дорога в городе ZooVille представляет собой n ям, расположенных в ряд. Будем считать, что ямы пронумерованы от 1 до n слева направо.

Илья очень хочет помочь своему городу, для этого он хочет отремонтировать хотя бы k ям (хотя можно и больше) на единственной дороге ZooVille.

В городе есть m строительных компаний, i-ая компания может за ci денежных единиц отремонтировать отрезок дороги, на котором находятся ямы с номерами не меньше li и не больше ri. Компании в городе ZooVille очень меркантильные, поэтому, если какая-то яма на ремонтируемом отрезке дороги уже отремонтирована, то стоимость ремонта отрезка дороги не уменьшается.

Определите, какое минимальное количество денег потребуется Илье, чтобы отремонтировать хотя бы k ям.

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

В первой строке записаны три целых числа n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 105, 1 ≤ k ≤ n). В следующих m строках записано описание компаний. В i-той строке записаны три целых числа li, ri, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ci ≤ 109).

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

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

Если отремонтировать хотя бы k ям невозможно, выведите -1.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.

Примеры
Входные данные
10 4 6
7 9 11
6 9 13
7 7 7
3 5 6
Выходные данные
17
Входные данные
10 7 1
3 4 15
8 9 8
5 6 8
9 10 6
1 4 2
1 4 10
8 10 13
Выходные данные
2
Входные данные
10 1 9
5 10 14
Выходные данные
-1