7225번 - Elektromobilis 다국어

Vytautas nori aplankyti draugą Vytį savo nauju žvilgančiu elektromobiliu. Abu draugai gyvena Bitlandijoje, kurią sudaro N miestų, sunumeruotų nuo 1 iki N. Vytautas gyvena mieste nr. 1, o Vytis – N. Tarp Bitlandijos miestų nutiesta M dvipusio eismo kelių.

Pakeliui Vytautui gali tekti sustoti pasikrauti elektromobilį. Jei mieste i yra įkrovimo stotelė, ji įkrauna c_i kWh per valandą. Vytautas krauna elektromobilį sveikąjį valandų skaičių (taip jam lengviau planuoti laiką). Elektromobilio baterijos talpa yra K kWh. Jei baterija pasikrauna valandai nepasibaigus, Vytautas palieka automobilį prijungtą prie įkrovimo stotelės iki valandos pabaigos.

Bet kokį tiesioginį kelią tarp dviejų miestų Vytautas elektromobiliu įveikia per 1 valandą, sunaudodamas L kWh elektros energijos. Kadangi elektromobilis naujutėlis, kelionės pradžioje baterija tuščia.

Per kokį trumpiausią laiką Vytautas gali nuvažiuoti iš miesto 1 į miestą N, jei kiekvienas mašinos įkrovimas turi užtrukti sveikąjį skaičių valandų?

Pirmoje įvesties eilutėje pateikti 4 sveikieji skaičiai:

• N – miestų skaičius;
• M – kelių skaičius;
• K – elektromobilio baterijos talpa;
• L – elektros kiekis, kurį elektromobilis sunaudoja važiuodamas per valandą.

Antroje eilutėje pateikta N sveikųjų skaičių c_i (0 ≤ c_i ≤ K) – i-tajame mieste galima įkrauti c_i kWh per valandą (jei c_i = 0, tai tame mieste nėra įkrovimo stotelės).

Tolesnėse M eilučių pateikti tiesioginiai keliai. Kiekvienoje iš šių eilučių pateikti i-tojo kelio pradžios ir pabaigos miestai a_i ir b_i (1 ≤ a_i, b_i ≤ N).

Jums reikia išvesti vieną skaičių – kiek mažiausiai laiko užtruks nuvažiuoti iš miesto 1 į miestą N. Išveskite −1, jei tokia kelionė neįmanoma.

• 2 ≤ N ≤ 100 000
• 1 ≤ M ≤ 100 000
• 1 ≤ K, L ≤ 100
• a_i ≠ b_i
• tarp dviejų miestų eina ne daugiau kaip vienas tiesioginis kelias.