Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
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