האי שבו מתגורר JOI-kun נפל לפלישת זומבים. JOI-kun החליט להימלט אל המקלט שהוגדר כמקום הפינוי הבטוח ביותר באי.

האי שבו מתגורר JOI-kun מורכב מ-$N$ עיירות הממוספרות מעיירה $1$ ועד עיירה $N$, והעיירות מחוברות ביניהן באמצעות כבישים. ישנם $M$ כבישים באי, וכל כביש מחבר $2$ עיירות שונות. JOI-kun יכול לנוע בחופשיות בשני הכיוונים לאורך הכבישים, אך אינו יכול לעבור מעיירה אחת לאחרת אלא דרך הכבישים.

מספר עיירות נשלטות על ידי זומבים ולא ניתן לבקר בהן. עיירה שניתן להגיע אליה מעיירה הנשלטת על ידי זומבים באמצעות $S$ כבישים או פחות נקראת עיירה מסוכנת. כל עיירה אחרת נקראת עיירה לא מסוכנת.

ביתו של JOI-kun נמצא בעיירה $1$, ומקלט הפינוי נמצא בעיירה $N$. עיירה $1$ ועיירה $N$ אינן נשלטות על ידי זומבים. מאחר שהנסיעה בכבישי האי אורכת זמן רב, בכל פעם ש-JOI-kun עובר לעיירה כלשהי, עליו ללון לילה אחד בעיירת היעד. כאשר JOI-kun לן בעיירה לא מסוכנת, הוא מתאכסן בפונדק זול שעלות הלינה בו היא $P$ ין, ואילו כאשר הוא לן בעיירה מסוכנת, הוא מתאכסן בפונדק יוקרה עם שירותי אבטחה מעולים שעלות הלינה בו היא $Q$ ין. JOI-kun רוצה לנוע כך שעלות הלינה שלו תהיה זולה ככל האפשר ולהתפנות לעיירה $N$. אין צורך ללון בעיירה $1$ או בעיירה $N$.

מצאו את הערך המינימלי האפשרי של סך דמי הלינה הנדרשים כאשר JOI-kun נע מעיירה $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$ כבישים, $K$ מתוך $N$ העיירות נשלטות על ידי זומבים, ועיירות שניתן להגיע אליהן מעיירה הנשלטת על ידי זומבים באמצעות $S$ כבישים או פחות נקראות עיירות מסוכנות.

השורה ה-$2$ מכילה $2$ מספרים שלמים מופרדים ברווחים $P, Q$ ($1 \le P < Q \le 100000$). נתון זה מציין ש-JOI-kun לן בפונדק שעולה $P$ ין בעיירה לא מסוכנת ובפונדק שעולה $Q$ ין בעיירה מסוכנת.

השורה ה-$i$ ($1 \le i \le K$) מתוך $K$ השורות הבאות מכילה מספר שלם $C_i$ ($2 \le C_i \le N - 1$). נתון זה מציין שעיירה $C_i$ נשלטת על ידי זומבים. $C_1, \dots, C_K$ כולם שונים זה מזה.

השורה ה-$j$ ($1 \le j \le M$) מתוך $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-kun נע מעיירה $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$. לנים בפונדק זול שעולה $1000$ ין בעיירה $2$.
• עוברים מעיירה $2$ לעיירה $5$. לנים בפונדק זול שעולה $1000$ ין בעיירה $5$.
• עוברים מעיירה $5$ לעיירה $9$. לנים בפונדק זול שעולה $1000$ ין בעיירה $9$.
• עוברים מעיירה $9$ לעיירה $10$. לנים בפונדק זול שעולה $1000$ ין בעיירה $10$.
• עוברים מעיירה $10$ לעיירה $11$. לנים בפונדק זול שעולה $1000$ ין בעיירה $11$.
• עוברים מעיירה $11$ לעיירה $12$. לנים בפונדק יוקרה שעולה $6000$ ין בעיירה $12$.
• עוברים מעיירה $12$ לעיירה $13$. לא לנים בעיירה $13$.

כאשר JOI-kun נע במסלול זה, סך דמי הלינה הוא $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