313D орчуулах · Codeforces.mn

# Илья болон Зам
Ильягийн амьдардаг хотод замаас бусад бүх зүйл нь үнэхээр гайхалтай.
ЗооВиллэгийн зам дээр нь дараалсан $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 1 9
5 10 14

Гаралт

-1