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