Maksulised teelõigud

문제

Valitsusel on plaan maksustada mõned lõigud Tallinna--Tartu maanteel. Inimesed aga kipuvad tasulisi lõike võimalusel vältima, sõites neist kõrvalteid mööda ümber, kui nii on odavam. Sama kulu korral eelistab juht alati põhimaanteed.

Kohalikud elanikud aga saaks väga kurjaks, kui nende küla kaudu autod voorima hakkaks, ja valitsus kukuks. Nii soovib valitsus saada teemaksust võimalikult suurt kasu, aga samas vältida vihaseid elanikke.

Leida, kui suure summa ulatuses saab valitsus maksustada erinevaid teelõike Tallinna--Tartu põhimaanteel, nii et juhil, kes alustab ja lõpetab oma sõidu ükskõik millises põhimaantee punktis, on optimaalne sõita ainult mööda põhimaanteed.

Alguses on teada, et põhimaantee on optimaalne: selle otspunktide vahel ei leidu sellist teekonda, mis kasutaks mõnd kõrvalteed ning mille sõidukulu oleks väiksem kui kulu mööda põhimaanteed. Samuti on teada, et iga üksikut põhimaantee lõiku on võimalik teisi teelõike kasutades vältida, seega ühegi lõigu hinda ei saa tõsta piiramatult.

입력

Tekstifaili esimesel real on neli täisarvu $KK$, $RR$, $TT$ ja $T_{p}T\_p$, kus:

• $KK$ on kilomeetri läbimise kütusekulu sentides ($1\le K\le 1001\; \backslash le\; K\; \backslash le\; 100$),
• $RR$ on ristmike arv teedevõrgus ($2\le R\le 50002\; \backslash le\; R\; \backslash le\; 5\backslash ,000$; ristmikud on nummerdatud $0\dots R-10\; \backslash dots\; R-1$),
• $TT$ on nendevaheliste teelõikude arv ($2\le T\le 150002\; \backslash le\; T\; \backslash le\; 15\backslash ,000$),
• $T_{P}T\_P$ on põhimaantee teelõikude arv ($1\le T_P\le 10001\; \backslash le\; T\_P\; \backslash le\; 1\backslash ,000$).

Järgmisel $TT$ real on igaühel kolm täisarvu $R_{1}R\_1$, $R_{2}R\_2$ ja $PP$, mis näitavad, et ristmikke $R_{1}R\_1$ ja $R_{2}R\_2$ ühendab teelõik pikkusega $PP$ kilomeetrit (). Põhimaantee läbib ristmikud $0\dots T_{P}0\; \backslash dots\; T\_P$ numbrite kasvamise järjekorras ja selle lõigud on sisendis antud esimestena nende maanteel esinemise järjekorras.

출력

Tekstifaili väljastada üks täisarv: kõigi maksustavate lõikude koguhind.

5 6 8 3
0 1 2
1 2 3
2 3 2
0 4 2
1 4 2
1 5 3
2 5 2
3 5 3

15