Relvaturg

문제

Umeerika Ühendriigid koosnevad $NN$ osariigist, mis on nummerdatud $1\dots N1\; \backslash ldots\; N$. Jussi kodu asub osariigis $NN$. Seal on tavaks hinnata mehe kõvadust selle järgi, kui palju tal tulirelvi on. Juss soovib olla kõva mees ja seega otsustas ta külastada sel aastal toimuvat kõrgtehnoloogiliste tulirelvade turgu osariigis $11$.

Jussi õnneks võeti osariigis $11$ just vastu "patriootliku enesekaitse seadus", millega seoses osariik maksab kinni kõik eraisikute poolt relvaturult ostetud tulirelvad, seega võib Juss sealt hankida nii palju relvi kui ta tahab.

Erinevate globaalsete kriiside tõttu on aga bensiin väga kallis ja seda saab Juss tagasisõiduks hankida ainult $KK$ ühikut. Osariigid on omavahel ühendatud $MM$ kahesuunalise kiirteega ja ühe ühiku bensiiniga on võimalik läbida teepikkus $11$~km. Kahte osariiki võib ühendada rohkem kui üks kiirtee.

Lisaks ei ole mitte kõik osariigid väga entusiastlikud oma tänavail miljoneid relvi nägema. Seetõttu on erinevates osariikides erinevad piirangud sellele, kui palju relvi võib üks isik endaga kaasas kanda. Osariigis $ii$ võib eraisik kaasas kanda ülimalt $C_{i}C\_i$ tulirelva.

Arvuta, kui palju relvi saab Juss maksimaalselt koju viia, arvestades nii piiratud bensiini hulka kui ka läbitavate osariikide kitsendusi relvade veole.

입력

Tekstifaili esimesel real on kolm täisarvu $NN$, $MM$ ja $KK$ ($2\le N\le {10}^{5}2\; \backslash le\; N\; \backslash le\; 10^5$, $1\le M\le {10}^{5}1\; \backslash le\; M\; \backslash le\; 10^5$, $1\le K\le {10}^{9}1\; \backslash le\; K\; \backslash le\; 10^9$), mis näitavad osariikide arvu, kiirteede arvu ja tagasisõiduks ostetava bensiini hulka.

Teisel real on $NN$ tühikutega eraldatud täisarvu $c_{i}c\_i$ ($-1\le c_i\le {10}^9)-1\; \backslash le\; c\_i\; \backslash le\; 10^9)$, kus $c_{i}c\_i$ näitab osariigis $ii$ kehtivat piirangut kaasaskantavate tulirelvade arvule (kui $c_i=-1c\_i\; =\; -1$, siis piirangut ei ole). Võib eeldada, et osariikides $11$ ja $NN$ piiranguid ei ole.

Viimasel $MM$ real on igaühel antud kolm täisarvu $A_{i}A\_i$, $B_{i}B\_i$ ja $L_{i}L\_i$ ($1\le L_i\le {10}^{9}1\; \backslash le\; L\_i\; \backslash le\; 10^9$), mis tähistavad, et osariike $A_{i}A\_i$ ja $B_{i}B\_i$ ühendab kiirtee pikkusega $L_{i}L\_i$~km. Võib eeldada, et $KK$ ühiku bensiiniga on Jussil võimalik koju sõita.

출력

Tekstifaili ainsale reale väljasta üks täisarv, mis näitab, kui palju tulirelvi Juss saab koju tagasi viia, või $-1-1$, kui ta saab viia piiramatu koguse relvi.

6 7 54
-1 15 99 20 25 -1
1 2 10
2 6 15
1 3 50
3 6 20
1 4 14
4 5 18
5 6 22

20