В городе Ильи все хорошо, кроме дорог, потому что единственная дорога в городе ZooVille представляет собой n ям, расположенных в ряд. Будем считать, что ямы пронумерованы от 1 до n слева направо.
Илья очень хочет помочь своему городу, для этого он хочет отремонтировать хотя бы k ям (хотя можно и больше) на единственной дороге ZooVille.
В городе есть m строительных компаний, i-ая компания может за ci денежных единиц отремонтировать отрезок дороги, на котором находятся ямы с номерами не меньше li и не больше ri. Компании в городе ZooVille очень меркантильные, поэтому, если какая-то яма на ремонтируемом отрезке дороги уже отремонтирована, то стоимость ремонта отрезка дороги не уменьшается.
Определите, какое минимальное количество денег потребуется Илье, чтобы отремонтировать хотя бы k ям.
Выходные данные
Выведите единственное целое число — минимальное количество денег, которое потребуется Илье, чтобы отремонтировать хотя бы k ям.
Если отремонтировать хотя бы k ям невозможно, выведите -1.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.