Contest Duration: - (local time) (200 minutes)
F - Find the Route! /

Time Limit: 2 sec / Memory Limit: 512 MB

Max Score: 1150 Points

### Problem Statement

There is a grid which size is $H \times W$. the upper-left cell is $(1,1)$ and the lower-right cell is $(H,W)$.
There is $N$ arrows. Arrow which start point is $(a_i,b_i)$ of direction is $c_i$, and size is $d_i$. ($d_i$ may be negative)
It is guaranteed that there are no two arrow which start point is same.

Sothe want to move from cell $(sx,sy)$ to cell $(gx,gy)$ with arrows.
But it may not possible to move to goal in initial grid.
So, Snuke decided to change some arrows.

Sothe can change each arrow as follows:
• He can't change the start point of this arrow.
• It costs $e_i$ if he change the direction of this arrow.
• It costs $f \times |d_i-G|$ if he change d_i to $G$.

He can't add or erase arrows.

Please calculate the minimum cost that he can move to $(gx,gy)$.

### If he can't move to goal, please output '-1'.

Note: Arrows are directed, and he can't turn in the middle of the arrow.

### Input

The input is given from standard input in the following format.

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


### Output

• Please output a single integer: The minimum cost to clear this puzzle.
• If you can't achieve the objective, print -1.
• Print \n (line break) in the end.

### Constraints

• $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$ is N, E, S, or W, which means North, East, South, West.

Subtask 1 [ 190 points ]

• $H=1$
• $W \le 600$

Subtask 2 [ 170 points ]

• $H,W \le 80$

Subtask 3 [ 360 points ]

• $H,W \le 600$

Subtask 4 [ 430 points ]

• There is no additional constraints.

### Sample Input 1

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


### Sample Output 1

4


### Sample Input 2

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


### Sample Output 2

14


### Sample Input 3

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


### Sample Output 3

14


### Sample Input 4

5 5 7 10
1 2 4 5
1 2 E 2 6
2 3 S 2 7
3 1 N 1 8
3 2 W 1 10
4 1 E 4 12
5 5 N 3 13
5 1 E 2 14


### Sample Output 4

14


### 問題文

$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」と出力すること。

### 入力

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行に出力しなさい。
また、最後には改行を入れること。

### 制約

• $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は東方向。

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

• H,W≦80を満たす。

• H,W≦600を満たす。

• 追加の制約はない。

### 入力例1

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


### 出力例1

4


### 入力例2

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


### 出力例2

14


### 入力例3

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


### 出力例3

14


### 入力例4

5 5 7 10
1 2 4 5
1 2 E 2 6
2 3 S 2 7
3 1 N 1 8
3 2 W 1 10
4 1 E 4 12
5 5 N 3 13
5 1 E 2 14


### 出力例4

14