AT_s8pc_4_f.Find the Route!

有一个 $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 \times |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 \leq H,W \leq 100000$
• $1 \leq N \leq 70000$
• $1 \leq f, e_i \leq 1000000$
• $1 \leq d_i \leq 100000$
• $1 \leq a_i, sx, tx \leq H$
• $1 \leq b_i, sy, ty \leq W$
• $c_i$ 为 'N', 'E', 'S', 'W' 其中之一。'N' 表示北侧（上方），'E' 表示东侧（右方）。

小子任务

小子任务1【190分】

• 满足 $H = 1$。
• 满足 $W \leq 600$。

小子任务2【170分】

• 满足 $H,W \leq 80$。

小子任务3【360分】

• 满足 $H,W \leq 600$。

小子任务4【430分】

• 无附加限制。

由 ChatGPT 5 翻译