{"problem":{"name":"Find the Route!","description":{"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)$.   There is $N$ arrows. Arrow which start point is $(a_i,b_i)$ of direction is $c_i$, an","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"s8pc_4_f"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"s8pc_4_f","tags":[],"sample_group":[],"created_at":"2026-03-03 11:01:14"}}