D. Илья болон Зам

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ильягийн амьдардаг хотод замаас бусад бүх зүйл нь үнэхээр гайхалтай. ЗооВиллэгийн зам дээр нь дараалсан $n$ ширхэг нүх үүссэн. Эдгээр нүхнүүдийг зүүнээс баруун тийш нь $1$-с $n$ хүртэл дугаарласан.

Илья өөрийн хотын хөгжилд маш их анхаардаг. Тэр зам дээрх дор хаяж $k$(их байж болно) ширхэг нүхийг бөглөхийг хүссэн.

Энэ хот нь $m$ барилгын компанитай. $i$ дугаар компани нь $l_i$-с $r_i$ хоорондох замыг $c_i$ төгрөгөөр засдаг. Тэдгээр компаний эзэд нь маш нарын хүмүүс учраас хэдэн ч нүх зассан хамаагүй заасан завсраараа л мөнгөө авдаг. Засаж буй завсарт нь засагдсан нүх орсон байсан ч хамаагүй $c$ төгрөгөө л авдаг гэсэн үг.

Илья хамгийн багадаа хэдэн төгрөгөөр дор хаяж $к$ ширхэг нүхийг засуулах вэ?

Оролт

Эхний мөрөнд $n, m, k (1 ≤ n ≤ 300, 1 ≤ m ≤ 10^5, 1 ≤ k ≤ n)$ гурван тоо байна. Дараагийн $m$ ширхэг мөр бүрт $ l_i, r_i, c_i (1 ≤ l_i ≤ r_i ≤ n, 1 ≤ c_i ≤ 10^9).$ гурван тоо байрлана.

Гаралт

Хамгийн бага зардал болох ганц тоо хэвлэнэ.

Боломжгүй тохиолдолд $"-1"$-г хэвлэнэ үү. Өөрөөр хэлбэл $к$ ширхэг нүх засч чадахгүй тохиолдолд.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Хүрэлцоож

Жишээ тэстүүд

Оролт
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
Сэтгэгдлүүдийг ачааллаж байна...