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