{"raw_statement":[{"iden":"background","content":"小蓝在 $L$ 市开出租车。"},{"iden":"statement","content":"$L$ 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行, 南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。\n\n从北到南一共有 $n$ 条东西向道路，依次标号为 $H_{1}, H_{2}, \\cdots, H_{n}$ 。从西到东 一共有 $m$ 条南北向的道路，依次标号为 $S_{1}, S_{2}, \\cdots, S_{m}$ 。\n\n每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，$H_{i}$ 与 $S_{j}$ 的交叉路口记为 $(i, j)$ 。\n\n从 $H_{1}$ 和 $S_{1}$ 的交叉路口 $(1,1)$ 开始，向南遇到的路口与 $(1,1)$ 的距离分别 是 $h_{1}, h_{2}, \\cdots, h_{n-1}$，向东遇到路口与 $(1,1)$ 的距离分别是 $w_{1}, w_{2}, \\cdots, w_{m-1}$ 。\n\n道路的每个路口都有一个红绿灯。\n\n时刻 $0$ 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段时间（每个路口不同)，然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。\n\n已知路口 $(i, j)$ 的南北向绿灯每次持续的时间为 $g_{i j}$, 东西向的绿灯每次持续的时间为 $r_{i j}$, 红绿灯的变换时间忽略。\n\n当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为看到绿灯；如果刚好由绿灯变为红灯，则视为看到红灯。\n\n每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头, 只能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。\n\n小蓝时刻 $0$ 从家出发。今天，他接到了 $q$ 个预约的订单，他打算按照订单 的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。小蓝的家在两个路口的中点，小蓝喜欢用 $x_{1}, y_{1}, x_{2}, y_{2}$ 来表示自己家的位 置, 即路口 $\\left(x_{1}, y_{1}\\right)$ 到路口 $\\left(x_{2}, y_{2}\\right)$ 之间的道路中点的右侧, 保证两个路口相邻 (中间没有其他路口)。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。\n\n小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能揷队完成后面的订单。\n\n小蓝只对 $L$ 市比较熟，因此他只会在给定的 $n$ 条东西向道路和 $m$ 条南北向道路上行驶，而且不会驶出 $H_{1}, H_{n}, S_{1}, S_{m}$ 这几条道路所确定的矩形区域 (可 以到边界。\n\n小蓝行车速度一直为 $1$，乘客上下车的时间忽略不计。\n\n请问，小蓝最早什么时候能完成所有订单回到家。"},{"iden":"input","content":"输入第一行包含两个整数 $n, m$，表示东西向道路的数量和南北向道路的数 量。\n\n第二行包含 $n-1$ 个整数 $h_{1}, h_{2}, \\cdots, h_{n-1}$ 。\n\n第三行包含 $m-1$ 个整数 $w_{1}, w_{2}, \\cdots, w_{m-1}$ 。\n\n接下来 $n$ 行, 每行 $m$ 个整数，描述每个路口南北向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $g_{i j}$ 。\n\n接下来 $n$ 行, 每行 $m$ 个整数，描述每个路口东西向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $r_{i j}$ 。\n\n接下来一行包含四个整数 $x_{1}, y_{1}, x_{2}, y_{2}$，表示小蓝家的位置在路口 $\\left(x_{1}, y_{1}\\right)$ 到路口 $\\left(x_{2}, y_{2}\\right)$ 之间的道路中点的右侧。\n\n接下来一行包含一个整数 $q$，表示订单数量。\n\n接下来 $q$ 行，每行描述一个订单，其中第 $i$ 行包含八个整数 $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}$，$x_{i 3}, y_{i 3}, x_{i 4}, y_{i 4}$，表示第 $i$ 个订单的起点为路口 $\\left(x_{i 1}, y_{i 1}\\right)$ 到路口 $\\left(x_{i 2}, y_{i 2}\\right)$ 之间的道 路中点的右侧，第 $i$ 个订单的终点为路口 $\\left(x_{i 3}, y_{i 3}\\right)$ 到路口 $\\left(x_{i 4}, y_{i 4}\\right)$ 之间的道路中 点的右侧。 "},{"iden":"output","content":"输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入保留一位小数。"},{"iden":"note","content":"**【样例说明】**\n\n蓝有一个订单, 他的行车路线如下图所示。其中 $\\mathrm{H}$ 表示他家的位置, $\\mathrm{S}$ 表示订单的起点, $\\mathrm{T}$ 表示订单的终点。小小明在最后回家时要在直行的红绿灯路 口等绿灯, 等待时间为 $20$。 \n\n![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_30_334c51de49a3a8e7ba1bg-15.jpg)\n\n**【评测用例规模与约定】**\n\n对于 $20 \\%$ 的评测用例, $1 \\leq n, m \\leq 5,1 \\leq q \\leq 10$ 。\n\n对于 $50 \\%$ 的评测用例, $1 \\leq n, m \\leq 30,1 \\leq q \\leq 30$ 。\n\n对于所有评测用例, $1 \\leq n, m \\leq 100,1 \\leq q \\leq 30,1 \\leq h_{1}<h_{2}<\\cdots<h_{n-1} \\leq$ $100000,1 \\leq w_{1}<w_{2}<\\cdots<w_{m-1} \\leq 100000,1 \\leq g_{i j} \\leq 1000,1 \\leq r_{i j} \\leq 1000$, 给定的路口一定合法。 "}],"translated_statement":null,"sample_group":[["2 3\n200\n100 400\n10 20 10\n20 40 30\n20 20 20\n20 20 20\n2 1 1 1\n1\n2 2 1 2 1 2 1 3","1620.0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}