题目描述

小蓝在 L 市开出租车。

L 市的规划很规整，所有的路都是正东西向或者正南北向的，道路都可以看成直线段。东西向的道路互相平行，南北向的道路互相平行，任何一条东西向道路垂直于任何一条南北向道路。

从北到南一共有 $n$ 条东西向道路，依次标号为 $H_1,H_2,⋅⋅⋅,H_n$。从西到东一共有 $m$ 条南北向的道路，依次标号为 $S_1,S_2,⋅⋅⋅,S_m$。

每条道路都有足够长，每一条东西向道路和每一条南北向道路都相交，$H_i$ 与 $S_j$ 的交叉路口记为 $(i,j)$。

从 $H_1$ 和 $S_1$ 的交叉路口 $(1,1)$ 开始，向南遇到的路口与 $(1,1)$ 的距离分别是 $h_1,h_2,⋅⋅⋅,h_{n−1}$，向东遇到路口与 $(1,1)$ 的距离分别是 $w_1,w_2,⋅⋅⋅,w_{m−1}$。

道路的每个路口都有一个红绿灯。

时刻 0 的时候，南北向绿灯亮，东西向红灯亮，南北向的绿灯会持续一段时间（每个路口不同），然后南北向变成红灯，东西向变成绿灯，持续一段时间后，再变成南北向绿灯，东西向红灯。

已知路口 $(i,j)$ 的南北向绿灯每次持续的时间为 $g_{i,j}$，东西向的绿灯每次持续的时间为 $r_{i,j}$，红绿灯的变换时间忽略。

当一辆车走到路口时，如果是绿灯，可以直行、左转或右转。如果是红灯，可以右转，不能直行或左转。如果到路口的时候刚好由红灯变为绿灯，则视为看到绿灯，如果刚好由绿灯变为红灯，则视为看到红灯。

每段道路都是双向道路，道路中间有隔离栏杆，在道路中间不能掉头，只能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。

小蓝时刻 0 从家出发。今天，他接到了 $q$ 个预约的订单，他打算按照订单的顺序依次完成这些订单，就回家休息。中途小蓝不准备再拉其他乘客。

小蓝的家在两个路口的中点，小蓝喜欢用 $x_1,y_1,x_2,y_2$ 来表示自己家的位置，即路口 $(x_1,y_1)$ 到路口 $(x_2,y_2)$ 之间的道路中点的右侧，保证两个路口相邻中间没有其他路口）。请注意当两个路口交换位置时，表达的是路的不同两边，路中间有栏杆，因此这两个位置实际要走比较远才能到达。

小蓝的订单也是从某两个路口间的中点出发，到某两个路口间的中点结束。小蓝必须按照给定的顺序处理订单，而且一个时刻只能处理一个订单，不能图省时间而同时接两位乘客，也不能插队完成后面的订单。

小蓝只对 L 市比较熟，因此他只会在给定的 $n$ 条东西向道路和 $m$ 条南北向道路上行驶，而且不会驶出 $H_1,H_n,S_1,S_m$ 这几条道路所确定的矩形区域（可以到边界）。

小蓝行车速度一直为 1，乘客上下车的时间忽略不计。

请问，小蓝最早什么时候能完成所有订单回到家。

输入描述

输入第一行包含两个整数 $n,m$，表示东西向道路的数量和南北向道路的数 量。

第二行包含 $n−1$ 个整数 $h_1,h_2,⋅⋅⋅,h_{n−1}$。

第三行包含 $m−1$ 个整数 $w_1,w_2,⋅⋅⋅,w_{m−1}$。

接下来 $n$ 行，每行 $m$ 个整数，描述每个路口南北向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $g_{i,j}$。

接下来 $n$ 行，每行 $m$ 个整数，描述每个路口东西向绿灯的时间，其中的第 $i$ 行第 $j$ 列表示 $r_{ij}$。

接下来一行包含四个整数 $x_1,y_1,x_2,y_2$，表示小蓝家的位置在路口 $(x_1,y_1)$ 到路口 $(x_2,y_2)$ 之间的道路中点的右侧。

接下来一行包含一个整数 $q$，表示订单数量。

接下来 $q$ 行，每行描述一个订单，其中第 $i$ 行包含八个整数 $x_{i1},y_{i1},x_{i2},y_{i2},x_{i3},y_{i3},x_{i4},y_{i4}$，表示第 $i$ 个订单的起点为路口 $(x_{i1},y_{i1})$ 到路口 $(x_{i2},y_{i2})$ 之间的道路中点的右侧，第 $i$ 个订单的终点为路口 $(x_{i3},y_{i3})$ 到路口 $(x_{i4},y_{i4})$ 之间的道路中 点的右侧。

其中有 $(1≤n,m≤100，1≤q≤30，1≤h_1<h_2<⋅⋅⋅<h_{n−1}≤10^5，1≤w_1<w_2<⋅⋅⋅<w_{m−1}≤10^5，1≤g_{i,j}≤1000，1≤r_{ij}≤1000)$，给定的路口一定合法。

输出描述

输出一个实数，表示小蓝完成所有订单最后回到家的最早时刻。四舍五入保留一位小数

2 3
200
100 400
10 20 10
20 40 30
20 20 20
20 20 20
2 1 1 1
1
2 2 1 2 1 2 1 3

1620.0

样例说明

小蓝有一个订单，他的行车路线如下图所示。其中 H 表示他家的位置，S 表示订单的起点，T 表示订单的终点。小明在最后回家时要在直行的红绿灯路口等绿灯，等待时间为 20。

评测用例规模与约定：

对于 20% 的评测用例，$1 \leq n,m \leq 5，1 \leq q \leq 10$。

对于 50% 的评测用例，$1 \leq n,m \leq 30，1 \leq q \leq 30$。

对于所有评测用例，$1 \leq n,m \leq 100，1 \leq q \leq 30，1 \leq h_1 < h_2 < \dots < h_{n-1} \leq 100000，1 \leq w_1 < w_2 < \dots < w_{m-1} \leq 100000，1 \leq g_{ij} \leq 1000，1 \leq r_{ij} \leq 1000)$，给定的路口一定合法。