تعرضت الجزيرة التي يعيش فيها 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