F - Find the Route! Editorial /

Time Limit: 2 sec / Memory Limit: 512 MB

Max Score: 1150 Points
Task statement was updated.

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.

Subtasks

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

制約

  • $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$ 点 ]

  • 追加の制約はない。

入力例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