Eyjan þar sem JOI-kun býr hefur orðið fyrir innrás uppvakninga. JOI-kun hefur ákveðið að flýja í neyðarskýlið sem er skilgreint sem öruggastirýmingarstaðurinn á eyjunni.

Eyjan þar sem JOI-kun býr samanstendur af $N$ bæjum sem eru númeraðir frá Bæ $1$ til Bæjar $N$, og bæirnir eru tengdir saman með vegum. Það eru $M$ vegir á eyjunni og hver vegur tengir saman $2$ ólíka bæi. JOI-kun getur ferðast frjálslega í báðar áttir eftir vegunum, en hann getur ekki farið frá einum bæ til annars nema eftir vegum.

Nokkrir bæir eru á valdi uppvakninga og ekki er hægt að heimsækja þá. Bær sem hægt er að komast til frá bæ á valdi uppvakninga með því að nota í mesta lagi $S$ vegi kallast hættulegur bær. Aðrir bæir kallast óhættulegir bæir.

Heimili JOI-kuns er í Bæ $1$ og neyðarskýlið er í Bæ $N$. Bær $1$ og Bær $N$ eru ekki á valdi uppvakninga. Þar sem það tekur langan tíma að ferðast um vegi eyjarinnar verður JOI-kun að gista eina nótt í áfangabænum í hvert sinn sem hann ferðast á milli bæja. Þegar JOI-kun gistir í óhættulegum bæ gistir hann á ódýru gistihúsi þar sem gistikostnaðurinn er $P$ jen, en þegar hann gistir í hættulegum bæ gistir hann á lúxusgistihúsi með framúrskarandi öryggisþjónustu þar sem gistikostnaðurinn er $Q$ jen. JOI-kun vill ferðast þannig að gistikostnaðurinn verði sem ódýrastur og komast í skjól í Bæ $N$. Hann þarf ekki að gista í Bæ $1$ né Bæ $N$.

Finndu minnsta mögulega heildargistikostnað sem þarf þegar JOI-kun ferðast frá Bæ $1$ til Bæjar $N$.

Inntak

Inntakið samanstendur af $2 + K + M$ línum.

$1$. línan inniheldur $4$ heiltölur aðskildar með bilum $N, M, K, S$ ($2 \le N \le 100000$, $1 \le M \le 200000$, $0 \le K \le N - 2$, $0 \le S \le 100000$). Þetta gefur til kynna að eyjan samanstandi af $N$ bæjum og $M$ vegum, að $K$ af þessum $N$ bæjum séu á valdi uppvakninga, og að bæir sem hægt er að komast til frá bæ á valdi uppvakninga eftir í mesta lagi $S$ vegum kallist hættulegir bæir.

$2$. línan inniheldur $2$ heiltölur aðskildar með bili $P, Q$ ($1 \le P < Q \le 100000$). Þetta gefur til kynna að JOI-kun gisti á gistihúsi sem kostar $P$ jen í óhættulegum bæ og á gistihúsi sem kostar $Q$ jen í hættulegum bæ.

$i$-ta línan ($1 \le i \le K$) af næstu $K$ línum inniheldur heiltölu $C_i$ ($2 \le C_i \le N - 1$). Þetta gefur til kynna að Bær $C_i$ sé á valdi uppvakninga. $C_1, \dots, C_K$ eru allar ólíkar.

$j$-ta línan ($1 \le j \le M$) af næstu $M$ línum inniheldur $2$ heiltölur aðskildar með bili $A_j, B_j$ ($1 \le A_j < B_j \le N$). Þetta gefur til kynna að vegur liggi á milli Bæjar $A_j$ og Bæjar $B_j$. Sama parið $(A_j, B_j)$ kemur ekki fyrir $2$ sinnum eða oftar.

Í gefnum inntaksgögnum er tryggt að hægt sé að ferðast frá Bæ $1$ til Bæjar $N$ með því að fara eingöngu um bæi sem eru ekki á valdi uppvakninga.

Úttak

Prentið í $1$ línu minnsta mögulega heildargistikostnað sem þarf þegar JOI-kun ferðast frá Bæ $1$ til Bæjar $N$.

Athugið að svarið rúmast ekki endilega innan sviðs $32$-bita heiltölu með formerki.

Dæmi

Inntak 1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

Úttak 1

11000

Skýring 1

Dæmi $1$ samsvarar myndinni hér að neðan. Hringir tákna bæi og línur tákna vegi.

Í þessu tilfelli eru Bær $3$, Bær $4$, Bær $6$, Bær $8$ og Bær $12$ hættulegir bæir.

Með því að ferðast á milli bæja í eftirfarandi röð má lágmarka heildargistikostnaðinn:

• Fara frá Bæ $1$ til Bæjar $2$. Gista á ódýru gistihúsi sem kostar $1000$ jen í Bæ $2$.
• Fara frá Bæ $2$ til Bæjar $5$. Gista á ódýru gistihúsi sem kostar $1000$ jen í Bæ $5$.
• Fara frá Bæ $5$ til Bæjar $9$. Gista á ódýru gistihúsi sem kostar $1000$ jen í Bæ $9$.
• Fara frá Bæ $9$ til Bæjar $10$. Gista á ódýru gistihúsi sem kostar $1000$ jen í Bæ $10$.
• Fara frá Bæ $10$ til Bæjar $11$. Gista á ódýru gistihúsi sem kostar $1000$ jen í Bæ $11$.
• Fara frá Bæ $11$ til Bæjar $12$. Gista á lúxusgistihúsi sem kostar $6000$ jen í Bæ $12$.
• Fara frá Bæ $12$ til Bæjar $13$. Gista ekki í Bæ $13$.

Þegar JOI-kun ferðast eftir þessari leið verður heildargistikostnaðurinn $11000$ jen, svo prentað er $11000$.

Inntak 2

21 26 2 2
1000 2000
5
16
1 2
1 3
1 10
2 5
3 4
4 6
5 8
6 7
7 9
8 10
9 10
9 11
11 13
12 13
12 15
13 14
13 16
14 17
15 16
15 18
16 17
16 19
17 20
18 19
19 20
19 21

Úttak 2

15000