Монгол улсын шинэ ерөнхийлөгч сургууль бүрт өдөр бүр үнэгүйгээр, шим тэжээлтэй хоол өгөх шинэ бодлого гаргажээ. Энэхүү бодлогыг хэрэгжүүлэхийн тулд Ерөнхийлөгч Улаанбаатар хотод ажиллахаар нэгэн элчийг илгээв. Ерөнхийлөгчийн тушаалаар Улаанбаатар хотын \(1\)-ээс \(N\) хүртэл дугаарлагдсан сургууль бүр өдөрт хамгийн багадаа \(K\) ширхэг шим тэжээлтэй хоол хүлээлгэн өгөх ёстой. Элч даалгаврыг биелүүлэхийн тулд \(M\) ширхэг "супер хүч" (superpowers)-ийг бэлджээ. Супер хүч бүр нь \(L_i\) болон \(R_i\) гэсэн параметртэй бөгөөд уг хүчийг ашигласнаар \(L_i\)-ээс \(R_i\) дугаартай бүх сургуульд тус бүр 1 ширхэг хоол хүргэгдэнэ. Супер хүч бүрийг идэвхжүүлэх зардал нь 1 төгрөг (энерги) юм. Элч өөрийн төгрөгийг хэмнэхийг хүсэж байгаа тул ерөнхийлөгчийн даалгаврыг биелүүлэхэд шаардагдах хамгийн бага төгрөгийн хэмжээг ол. Хэрэв даалгаврыг биелүүлэх боломжгүй бол \(-1\)-ийг хэвлэнэ үү.

Оролт:

Эхний мөрөнд \(N, M, K\) гэсэн гурван бүхэл тоо өгөгдөнө.

Дараагийн \(M\) мөр бүрт супер хүч бүрийн хамрах хүрээг илэрхийлэх \(L_i, R_i\) тоо өгөгдөнө.

Гаралт

Даалгаврыг биелүүлэхэд шаардагдах хамгийн бага төгрөгний хэмжээг илэрхийлэх нэг бүхэл тоог хэвлэ. Боломжгүй бол \(-1\)-ийг хэвлэ.

Хязгаарлалт:

• \(1 \le N \le 2 \times 10^5\)
• \(1 \le K \le M \le 2 \times 10^5\)
• \(1 \le L_i \le R_i \le N\)

Дэд бодлогууд:

Жишээ

Оролт 1

5 4 2
1 3
2 4
3 5
1 5

Гаралт 1

3

Оролт 2

8 3 3
1 8
1 8
1 7

Гаралт 2

-1

Тайлбар:

Бүх супер хүчийг ашигласан ч 8-р сургууль ердөө 2 хоол авах тул \(K=3\) нөхцөлийг хангах боломжгүй.