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 翻译