AT_joi2016yo_e ゾンビ島 (Zombie Island)

[problemUrl]: https://atcoder.jp/contests/joi2016yo/tasks/joi2016yo_e 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\ \leqq\ N\ \leqq\ 100\,000 $，$ 1\ \leqq\ M\ \leqq\ 200\,000 $，$ 0\ \leqq\ K\ \leqq\ N\ -\ 2 $，$ 0\ \leqq\ S\ \leqq\ 100\,000 $) が空白を区切りとして書かれている．これは，島が $ N $ 個の町と $ M $ 本の道路からなり，$ N $ 個の町のうち $ K $ 個の町がゾンビに支配されており，ゾンビに支配されている町から $ S $ 本以下の道路を使って到達できる町を危険な町と呼ぶことを表す． $ 2 $ 行目には，$ 2 $ つの整数 $ P,\ Q $ ($ 1\ \leqq\ P\

JOI 君が町 $ 1 $ から町 $ N $ まで移動するときに必要な宿泊費の合計の最小値を $ 1 $ 行で出力せよ． 出力が $ 32 $ ビット符号付き整数の範囲に収まるとは限らないことに注意せよ． - - - - - -

### Sample Explanation 1 入出力例 $ 1 $ は，以下の図に対応している．円は町を，線は道路を表す． !\[2016-yo-t5-fig01.png\](https://img.atcoder.jp/joi2016yo/2016-yo-t5-fig01.png) この場合，町 $ 3 $，町 $ 4 $，町 $ 6 $，町 $ 8 $，町 $ 12 $ が危険な町である． 以下のような順番で町を移動すると，宿泊費の合計を最小にできる． - 町 $ 1 $ から町 $ 2 $ に行く．町 $ 2 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 2 $ から町 $ 5 $ に行く．町 $ 5 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 5 $ から町 $ 9 $ に行く．町 $ 9 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 9 $ から町 $ 10 $ に行く．町 $ 10 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 10 $ から町 $ 11 $ に行く．町 $ 11 $ で宿泊費が $ 1\,000 $ 円の安い宿に宿泊する． - 町 $ 11 $ から町 $ 12 $ に行く．町 $ 12 $ で宿泊費が $ 6\,000 $ 円の高級宿に宿泊する． - 町 $ 12 $ から町 $ 13 $ に行く．町 $ 13 $ では宿泊しない． JOI 君がこのような経路で移動したとき，宿泊費の合計は $ 11\,000 $ 円になるので，$ 11\,000 $ を出力する． - - - - - -