5. Letné nakupovanie

Prišlo leto a s ním aj LTT. Úžasná akcia, ktorej sa chce každý nadšený matematik, fyzik či informatik zúčastniť. Vedúci si na sústredenie prichystali množstvo zaujímavých prednášok. Keď však dorazili na chatu, zistili, že väčšina ich fixiek nepíše. Na vedúcovskej izbe zavládol nepokoj. Čo budú robiť? Aké vedomosti si účastníci z tábora odnesú, ak nikto nebude môcť vysvetľovať na tabuľu? Nuž, podujali sa fixky vo veľkom množstve nakúpiť. Zásoby v jednotlivých dedinách naokolo sú však obmedzené a z miest, ako tak blízko k chate, to bude isto nejaký čas trvať. Oni však majú málo penazí a tiež by chceli, aby fixky prišli čím skôr. Vymyslite, ako im s týmto problémom pomôcť a čo najskôr k ním fixky dopraviť.

Úloha

V úlohe dostanete pre každý obchod počet fixiek, ktoré má na sklade – \(p_i\) a cenu za jeden kus – \(c_i\). Naviac od nás dostanete informáce o tom, ktoré obchody sú s ktorými priamo prepojené cestou. Môžete predpokladať, že prevoz fixiek medzi nejakými priamo spojenými obchodmi trvá nejaký konštantný čas, napr. \(1\) hodinu. Vašou úlohou je nájsť najmenší čas \(t\), za ktorý je možné dopraviť \(p\) fixiek na chatu za cenu najviac \(c\). Znamená to teda, že vašou hlavnou úlohou je minimalizovať čas, za ktorý fixky dorazia na chatu, nie celkovú cenu, tá samozrejme ale musí byť dostatočne malá aby bola zaplatiteľná vedúcimi.

Formát vstupu

Na začiatku vstupu sa nachádzajú \(4\) čísla \(n\), \(m\), \(p\), \(c\). Číslo \(n\) (\(1 \leq n \leq 100\,000\)) – počet obchodov, ktoré sa nachádzajú v okolitých dedinách, \(m\) (\(1 \leq m \leq 1\,000\,000\)) – počet spojení medzi obchodmi ale aj chatou a potom \(p\) (\(1 \leq p \leq 10^7\)) a \(c\) (\(1 \leq c \leq 10^9\)), počet fixiek, ktoré chceme nakúpiť a maximálna cena, ktorú si môžme dovoliť zaplatiť. Chata má v našom číslovaní vždy číslo \(n\) a nepočíta sa medzi obchody. Na ďaľšom riadku je \(n\) medzerou oddelených čísel, ktoré reprezentujú \(p_i\)(\(0 \leq p_i \leq 10^7\)). \(i\)-te číslo na tomto riadku určuje počet fixiek, ktoré má na sklade \(i\)-ty obchod. Na ďaľšom riadku je \(n\) medzerou oddelených čísel, ktoré reprezentujú \(c_i\)(\(0 \leq c_i \leq 10^9\)). \(i\)-te číslo na tomto riadku určuje cenu jednej fixky v \(i\)-tom obchode. Na nasledujúcich \(m\) riadkoch sú postupne dvojice čísel \(a\), \(b\) (\(0 \leq a, b \leq n\)), reprezentujúce, že existuje priama a obojsmerná cesta medzi lokáciami(chata/obchod) s číslom \(a\) a \(b\). Všimnite si, že napriek tomu, že obchody číslujeme od \(0\), \(a\), či \(b\) môžu byť aj rovné \(n\), čo symbolizuje cestu, ktorá spája nejaký obchod a chatu. Možete predpokladať, že z každej lokácie sa dá dostať do každej inej lokácie postupnosťou nejakých priamych spojení.

Formát výstupu

Na výstup vypíšte jedno číslo – najmenší čas, za ktorý sa dá nakúpiť \(p\) fixiek, pričom ich cena dokopy nepresiahne cenu \(c\) alebo \(-1\) ak sa to nedá.

Hodnotenie

Pre jednotlivé sady platia aj tieto špeciálne obmedzenia:

V prvej sade platí, že počet obchodov je malý a takisto aj počet priamych ciest, teda \(n \leq 100\) a \(m \leq 150\). V druhej sade platí, že \(n \leq 10\,000\) a \(m \leq 50\,000\). Pre tretiu a štvrtú sadu neplatia žiadne špeciálne obmedzenia.

Príklad

Input:

4 4 10 32
7 3 5 4
9 2 3 4
0 4
1 4
2 4
3 2

Output:

2

V tomto pripade existujú obchody do vzdialenosti \(2\), ktoré nám spolu vedia dopraviť dosť fixiek za prijateľnú cenu. Konkrétne sú to obchody \(1\), \(2\) a \(3\). Môžme napr. vziať \(3\) fixky z obchodu \(1\), \(5\) fixiek z obchodu \(2\) a \(2\) fixky z obchodu \(3\). Za cenu \(3 \cdot 2 + 5 \cdot 3 + 2 \cdot 4 = 29\). Ak by sme hľadali riešenie do vzdialenosti \(1\), museli by sme nakúpiť fixky v obchode \(0\), ktorý je ale na naše dostupné prostriedky pridrahý.

Input:

4 5 5 20
10 3 1 2
7 4 4 6
4 3
4 2
1 0
4 1
3 0

Output:

-1

V tomto prípade neexistujú obchody, z ktorých by sme vedeli nakúpiť potrebné množstvo za nami požadovanú cenu.