| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 8 | 6 | 2 | 50.000% |
Umeerika Ühendriigid koosnevad $N$ osariigist, mis on nummerdatud 1ドル \ldots N$. Jussi kodu asub osariigis $N$. 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 1ドル$.
Jussi õnneks võeti osariigis 1ドル$ 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 $K$ ühikut. Osariigid on omavahel ühendatud $M$ kahesuunalise kiirteega ja ühe ühiku bensiiniga on võimalik läbida teepikkus 1ドル$~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 $i$ võib eraisik kaasas kanda ülimalt $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 $N,ドル $M$ ja $K$ (2ドル \le N \le 10^5,ドル 1ドル \le M \le 10^5,ドル 1ドル \le K \le 10^9$), mis näitavad osariikide arvu, kiirteede arvu ja tagasisõiduks ostetava bensiini hulka.
Teisel real on $N$ tühikutega eraldatud täisarvu $c_i$ ($-1 \le c_i \le 10^9),ドル kus $c_i$ näitab osariigis $i$ kehtivat piirangut kaasaskantavate tulirelvade arvule (kui $c_i = -1,ドル siis piirangut ei ole). Võib eeldada, et osariikides 1ドル$ ja $N$ piiranguid ei ole.
Viimasel $M$ real on igaühel antud kolm täisarvu $A_i,ドル $B_i$ ja $L_i$ (1ドル \le L_i \le 10^9$), mis tähistavad, et osariike $A_i$ ja $B_i$ ühendab kiirtee pikkusega $L_i$~km. Võib eeldada, et $K$ ü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,ドル 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