AT_s8pc_4_f Find the Route!

[problemUrl]: https://atcoder.jp/contests/s8pc-4/tasks/s8pc_4_f 配点： $ 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 $ 点 \] - 追加の制約はない。