Problem Description

Score: $ 1150 $ points
There is a grid of size $H \times W$. The top-left coordinate is $ (1,1) $ and the bottom-right coordinate is $ (H,W) $.
There are $ N $ squares with arrows drawn from them. The arrow from coordinate $ (a_i,b_i) $ points in direction $ c_i $ and travels a distance of $ d_i $.
Also, there are no multiple arrows from the same square.

E869120 wants to travel from coordinate $ (sx,sy) $ to $ (gx,gy) $ following only the arrows.
However, with the current board, it might not be possible to reach the goal.
Therefore, E869120 decided to modify the grid, but it costs something to modify the grid.

He can change the direction or distance of each arrow as follows:
- Changing the direction $ c_i $ costs $ e_i $.
- Changing the distance $ d_i $ to $ G $ costs $ f*|d_i-G| $. Here, $ |p| $ is the absolute value of $ p $. ( $ d_i $ can also take negative values. Also, $ f $ is a common value for all arrows)
- Note that $ d_i $ can be negative. In that case, the arrow reverses its direction, and its size becomes $ |d_i| $.

Find the minimum cost to modify the board so that it is possible to travel from the start to the goal following only the arrows.
If it is not possible to reach the goal even after modifying the grid, output "-1".

Note: The coordinate system here is represented as (p1,p2), where $ p1 $ smaller is towards the north and $ p2 $ smaller is towards the west.

Input Format

The input is given from the 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 Format

Output the minimum total cost to modify the arrows to reach from the start to the goal in one line.
Also, include a newline at the end.

Sample Input and Output

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

None

Sample Output #4

14

Notes/Hints

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 one of N, E, S, W. N is the upward direction, E is the east direction.

Subtasks

Subtask 1 \[ $ 190 $ points \]

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

Subtask 2 \[ $ 170 $ points \]

• Satisfies $H,W \le 80$.

Subtask 3 \[ $ 360 $ points \]

• Satisfies $H,W \le 600$.

Subtask 4 \[ $ 430 $ points \]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分