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ų.</p>

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:</p>

• 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.

예제 입력

5 5 13 11
7 10 1 10 2
1 2
1 3
2 4
3 5
4 5

예제 출력

7