เกาะที่ 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$ โดยผ่านเฉพาะเมืองที่ไม่ถูกซอมบี้ยึดครองได้

ข้อมูลส่งออก

แสดงผลรวมค่าที่พักที่น้อยที่สุดที่ต้องใช้เมื่อ JOI-kun เดินทางจากเมือง $1$ ไปยังเมือง $N$ ใน $1$ บรรทัด

โปรดระวังว่าผลลัพธ์อาจไม่อยู่ในช่วงของจำนวนเต็มแบบมีเครื่องหมายขนาด $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