Find the Route!

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$ [samples]