{"raw_statement":[{"iden":"problem statement","content":"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)$.  \nThere 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)  \nIt is guaranteed that there are no two arrow which start point is same.  \n  \nSothe want to move from cell $(sx,sy)$ to cell $(gx,gy)$ with arrows.  \nBut it may not possible to move to goal in initial grid.  \nSo, Snuke decided to change some arrows.  \n  \n\n![image](https://atcoder.jp/img/s8pc-4/5eff69da8ebd635a501515b7f86a47e6.png)\n\nSothe can change each arrow as follows:  \n\n*   He can't change the start point of this arrow.\n*   It costs $e_i$ if he change the direction of this arrow.\n*   It costs $f \\\\times |d_i-G|$ if he change $d_i$ to $G$.\n\n![image](https://atcoder.jp/img/s8pc-4/532f821bbe6594a29e622d7a81cbcad7.png)\n\n  \nHe can't add or erase arrows.  \n  \nPlease calculate the minimum cost that he can move to $(gx,gy)$.  \n\n### If he can't move to goal, please output '-1'.\n\nNote: Arrows are directed, and he can't turn in the middle of the arrow."},{"iden":"input","content":"The input is given from standard input in the following format.  \n  \n\n$H$ $W$ $N$ $f$\n$sx$ $sy$ $gx$ $gy$\n$a_1$ $b_1$ $c_1$ $d_1$ $e_1$\n$a_2$ $b_2$ $c_2$ $d_2$ $e_2$\n :   :   :\n$a_N$ $b_N$ $c_N$ $d_N$ $e_N$"},{"iden":"sample input 1","content":"4 4 2 2\n1 1 2 2\n1 1 E 1 1\n1 2 E 2 2"},{"iden":"sample output 1","content":"4"},{"iden":"sample input 2","content":"1 4 2 10\n1 1 1 4\n1 1 E 1 4\n1 3 W 1 4"},{"iden":"sample output 2","content":"14"},{"iden":"sample input 3","content":"1 8 4 9\n1 3 1 6\n1 1 E 7 2\n1 8 W 7 5\n1 3 W 2 5\n1 6 E 2 8"},{"iden":"sample output 3","content":"14"},{"iden":"sample output 4","content":"14"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}