Ir zināmi K vielu veidi un N alķīmisko reakciju tipi. Katra reakcija no noteikta vielu komplekta veido citu vielu komplektu. Katras reakcijas veikšanai nepieciešams stingri noteikts laiks. Katru vielu, kas iegūta reakcijas rezultātā, var izdalīt tīrā veidā izmantošanai citās reakcijās. Katras vielas daudzums vienmēr ir pietiekams jebkuras reakcijas veikšanai. Tikko notikušā reakcijā iegūtu vielu tūlīt pat var izmantot citu reakciju veikšanai. Vairākas reakcijas var notikt vienlaicīgi.

Uzrakstiet programmu, kas pēc dotās infomācijas par vielām un reakcijām nosaka mazāko laiku, kāds nepieciešams, lai iegūtu noteiktu vielu! 

Ievaddatu pirmā rinda satur četrus veselus skaitļus: K (3≤K ≤250) - dažādo vielu skaits, N (3≤N≤500) - dažādo reakciju skaits, M (1≤M<K) - sākumā pieejamo vielu skaits, kā arī tās vielas numurs, kuru nepieciešams iegūt.

Tālāk failā seko N bloki, katrs no kuriem apraksta vienu reakciju un sastāv no trim rindām - pirmā rinda satur naturālu skaitli - laiku, kas nepieciešams reakcijas norisei, otrā rinda satur to vielu skaitu, kas piedalās reakcijā un šo vielu numuru pārskaitījumu, bet trešā rinda - to vielu skaitu, kas tiek iegūtas reakcijas rezultātā un šo vielu numuru pārskaitījumu.

Vielas, kas ir pieejamas sākumā, ir sanumurētas pēc kārtas ar skaitļiem no 1 līdz M, bet visas pārējās - no M+1 līdz K. Visu reakciju norisei nepieciešamais laiks nepārsniedz 2*10^9. 

Izvaddatu vienīgajai rindai jāsatur viens vesels skaitlis - mazākais laiks, kāds nepieciešams, lai iegūtu noteikto vielu. Ja šo vielu iegūt nav iespējams, faila vienīgajā rindā jāizvada tikai skaitlis -1.

Dotajam piemēram vielu 4 var iegūt, ja trīs laika vienības notiek reakcija 2, bet pēc tam divas laika vienības notiek reakcija 3. Tādējādi, piecās laika vienībās būs iegūta vajadzīgā viela.

Uzdevums izmantots Ukrainas XVI.informātikas olimpiādē 2003.gadā