JOI-кун тұратын аралды зомбилер басып алды. JOI-кун аралдағы ең қауіпсіз эвакуация орны ретінде белгіленген панаға қашуды ұйғарды.

JOI-кун тұратын арал $1$-қаладан $N$-қалаға дейін нөмірленген $N$ қаладан тұрады, ал қалалар өзара жолдармен байланысқан. Аралда $M$ жол бар және әрбір жол әртүрлі $2$ қаланы қосады. JOI-кун жолдармен екі бағытта да еркін жүре алады, бірақ жолдардан тыс бір қаладан екінші қалаға бара алмайды.

Бірнеше қаланы зомбилер бақылауына алған және оларға бару мүмкін емес. Зомбилер бақылауындағы қаладан көп дегенде $S$ жолды пайдаланып жетуге болатын қала қауіпті қала деп аталады. Қалған қалалар қауіпті емес қалалар деп аталады.

JOI-кунның үйі $1$-қалада, ал эвакуациялық пана $N$-қалада орналасқан. $1$-қала мен $N$-қала зомбилердің бақылауында емес. Аралдың жолдарымен жүру көп уақыт алатындықтан, JOI-кун басқа қалаға барған сайын сол барған қаласында бір түн қонуы тиіс. JOI-кун қауіпті емес қалада қонғанда, қону ақысы $P$ иен тұратын арзан қонақүйге тоқтайды, ал қауіпті қалада қонғанда, қауіпсіздік қызметі өте жақсы, қону ақысы $Q$ иен тұратын қымбат қонақүйге тоқтайды. JOI-кун қону шығыны мүмкіндігінше арзан болатындай етіп жүріп, $N$-қалаға эвакуацияланғысы келеді. $1$-қала мен $N$-қалада қонудың қажеті жоқ.

JOI-кун $1$-қаладан $N$-қалаға дейін барғанда қажет болатын жалпы қону ақысының ең кіші мәнін табыңыз.

Кіріс деректер

Кіріс деректер $2 + K + M$ жолдан тұрады.

$1$-ші жолда бос орын арқылы бөлінген $4$ бүтін сан $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$) берілген. Бұл аралдың $N$ қала мен $M$ жолдан тұратынын, $N$ қаланың ішінде $K$ қала зомбилердің бақылауында екенін және зомбилер бақылауындағы қаладан көп дегенде $S$ жол арқылы жетуге болатын қалалар қауіпті қала деп аталатынын білдіреді.

$2$-ші жолда бос орын арқылы бөлінген $2$ бүтін сан $P, Q$ ($1 \le P < Q \le 100000$) берілген. Бұл JOI-кунның қауіпті емес қалада бағасы $P$ иен, ал қауіпті қалада бағасы $Q$ иен тұратын қонақүйге тоқтайтынын білдіреді.

Келесі $K$ жолдың $i$-ші жолында ($1 \le i \le K$) бүтін сан $C_i$ ($2 \le C_i \le N - 1$) жазылған. Бұл $C_i$-қала зомбилердің бақылауында екенін білдіреді. $C_1, \dots, C_K$ барлығы әртүрлі.

Келесі $M$ жолдың $j$-ші жолында ($1 \le j \le M$) бос орын арқылы бөлінген $2$ бүтін сан $A_j, B_j$ ($1 \le A_j < B_j \le N$) жазылған. Бұл $A_j$-қала мен $B_j$-қала арасында жол бар екенін білдіреді. Бірдей $(A_j, B_j)$ жұбы $2$ немесе одан көп рет кездеспейді.

Берілген кіріс деректерде тек зомбилер бақылауында емес қалалар арқылы өтіп, $1$-қаладан $N$-қалаға жетуге болатынына кепілдік беріледі.

Шығыс деректер

$1$ жолда JOI-кун $1$-қаладан $N$-қалаға барғанда қажет болатын жалпы қону ақысының ең кіші мәнін шығарыңыз.

Жауап $32$ биттік таңбалы бүтін сандар диапазонына сыймауы мүмкін екеніне назар аударыңыз.

Мысалдар

Кіріс 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

Шығыс 1

11000

Ескертпе 1

$1$-мысал төмендегі суретке сәйкес келеді. Шеңберлер қалаларды, ал сызықтар жолдарды білдіреді.

Бұл жағдайда $3$-қала, $4$-қала, $6$-қала, $8$-қала және $12$-қала қауіпті қалалар болып табылады.

Қалалар арасында келесі ретпен қозғалса, жалпы қону ақысын барынша азайтуға болады:

• $1$-қаладан $2$-қалаға бару. $2$-қалада бағасы $1000$ иен тұратын арзан қонақүйге қону.
• $2$-қаладан $5$-қалаға бару. $5$-қалада бағасы $1000$ иен тұратын арзан қонақүйге қону.
• $5$-қаладан $9$-қалаға бару. $9$-қалада бағасы $1000$ иен тұратын арзан қонақүйге қону.
• $9$-қаладан $10$-қалаға бару. $10$-қалада бағасы $1000$ иен тұратын арзан қонақүйге қону.
• $10$-қаладан $11$-қалаға бару. $11$-қалада бағасы $1000$ иен тұратын арзан қонақүйге қону.
• $11$-қаладан $12$-қалаға бару. $12$-қалада бағасы $6000$ иен тұратын қымбат қонақүйге қону.
• $12$-қаладан $13$-қалаға бару. $13$-қалада қонбау.

JOI-кун осы маршрутпен жүргенде, жалпы қону ақысы $11000$ иенді құрайды, сондықтан $11000$ шығарылады.

Кіріс 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

Шығыс 2

15000