题目描述

配点： $1150$ 点
$H\ \times\ W$のグリッドがあります。左上の座標は$(1,1)$で、右下の座標は$(H,W)$です。
$N$ 個のマスからは矢印が引かれており、座標$(a_i,b_i)$から出ている矢印の先は、方向$c_i$に、距離$d_i$飛んだ場所、となっています。
また、同じマスから複数の矢印が出ていることはありません。

そこで、E869120は座標$(sx,sy)$から$(gx,gy)$へ矢印のみをたどって行きたいと思っています。
しかし、今の盤面だとゴールまで行けない場合があります。
そこで、E869120はグリッドを変えることにしました。しかし、グリッドを変えるのにはコストがかかります。

彼は、各矢印の方向や向きを以下のように変えることができる。

• 方向$c_i$を変えるのにコスト$e_i$かかる。
• ・距離 $d_i$ の値を $G$ に変えるのに $f*|d_i-G|$ かかる。ただし、$|p|$ は $p$ の絶対値。（$d_i$ は負の値も取りうる。また、$f$はどの矢印についても共通の値である）
• ただし、$d_i$の値を負にしてもよい。その場合、その矢印は逆向きになり、矢印の大きさは $|d_i|$ となる。

そのとき、スタートからゴールまで矢印のみをたどって行けるような盤面にするための、最小コストを求めてください。
ただし、矢印は一方通行であり、矢印の途中で曲がったりすることはできないとします。

ただし、グリッドを変えてもゴールにたどり着けない場合、「-1」と出力すること。

注意：ここでいう座標系は、(p1,p2)という形で表され、$p1$が小さい方が北側、$p2$ が小さい方が左側（西側）である。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $N$ $f$ $sx$ $sy$ $gx$ $gy$ $a_1$ $b_1$ $c_1$ $d_1$ $e_1$ $a_2$ $b_2$ $c_2$ $d_2$ $e_2$ : : : $a_N$ $b_N$ $c_N$ $d_N$ $e_N$

输出格式

スタートからゴールにたどり着くための、矢印を変えるコストの合計を最小値を1行に出力しなさい。
また、最後には改行を入れること。

4 4 2 2
1 1 2 2
1 1 E 1 1
1 2 E 2 2

4

1 4 2 10
1 1 1 4
1 1 E 1 4
1 3 W 1 4

14

1 8 4 9
1 3 1 6
1 1 E 7 2
1 8 W 7 5
1 3 W 2 5
1 6 E 2 8

14

14

提示

制約

• $1\ \le\ H,W\ \le\ 100000$
• $1\ \le\ N\ \le\ 70000$
• $1\ \le\ f,e_i\ \le\ 1000000$
• $1\ \le\ d_i\ \le\ 100000$
• $1\ \le\ a_i,sx,tx\ \le\ H$
• $1\ \le\ b_i,sy,ty\ \le\ W$
• $c_i$はN,E,S,Wのどれかである。Nは上方向、Eは東方向。

小課題

小課題1 [ $190$点 ]

• H=1を満たす。
• W≦600を満たす。

小課題2 [ $170$ 点 ]

• H,W≦80を満たす。

小課題3 [ $360$ 点 ]

• H,W≦600を満たす。

小課題4 [ $430$ 点 ]

• 追加の制約はない。