Background

Xiao Lan drives a taxi in city $L$.

Problem Description

City $L$ is planned in a very regular way. All roads run either exactly east-west or exactly north-south, and each road can be regarded as a line segment. All east-west roads are parallel to each other, all north-south roads are parallel to each other, and any east-west road is perpendicular to any north-south road.

There are $n$ east-west roads from north to south, labeled $H_{1}, H_{2}, \cdots, H_{n}$ in order. There are $m$ north-south roads from west to east, labeled $S_{1}, S_{2}, \cdots, S_{m}$ in order.

Each road is long enough. Every east-west road intersects every north-south road. The intersection of $H_{i}$ and $S_{j}$ is called intersection $(i, j)$.

Starting from intersection $(1,1)$ of $H_{1}$ and $S_{1}$, the distances from $(1,1)$ to the intersections encountered when going south are $h_{1}, h_{2}, \cdots, h_{n-1}$, and the distances from $(1,1)$ to the intersections encountered when going east are $w_{1}, w_{2}, \cdots, w_{m-1}$.

Each intersection has a traffic light.

At time $0$, the north-south direction has a green light and the east-west direction has a red light. The north-south green light lasts for some time (which may differ for each intersection), then it turns red and the east-west direction turns green. After lasting for some time, it switches back to north-south green and east-west red, and so on.

At intersection $(i, j)$, each north-south green phase lasts $g_{i j}$, and each east-west green phase lasts $r_{i j}$. The switching time is ignored.

When a car arrives at an intersection: if the light is green, it may go straight, turn left, or turn right. If the light is red, it may turn right but may not go straight or turn left. If the light changes from red to green exactly at the arrival time, it is considered green; if it changes from green to red exactly at the arrival time, it is considered red.

Each road is two-way. There is a barrier in the middle of the road, so U-turns are not allowed in the middle of a road; a U-turn is only allowed at an intersection. When making a U-turn, it can be done regardless of whether the light is red or green. The time for a U-turn can be ignored.

Xiao Lan leaves home at time $0$. Today he received $q$ reserved orders. He plans to complete these orders one by one in the given order, and then go home to rest. He does not plan to take any other passengers in between. Xiao Lan’s home is at the midpoint between two intersections. He likes to use $x_{1}, y_{1}, x_{2}, y_{2}$ to describe the location of his home, meaning the right side of the midpoint of the road segment between intersections $\left(x_{1}, y_{1}\right)$ and $\left(x_{2}, y_{2}\right)$. It is guaranteed that the two intersections are adjacent (there is no other intersection between them). Note that swapping the two intersections describes the other side of the road. Because there is a barrier in the middle, these two positions are actually far apart in terms of driving distance.

Each order also starts from the right side of the midpoint between two intersections, and ends at the right side of the midpoint between two intersections. Xiao Lan must handle the orders in the given order, and at any time he can handle only one order. He cannot take two passengers at the same time to save time, and he cannot change the order by doing later orders first.

Xiao Lan is only familiar with city $L$, so he will only drive on the given $n$ east-west roads and $m$ north-south roads, and he will not leave the rectangular region determined by roads $H_{1}, H_{n}, S_{1}, S_{m}$ (he may reach the boundary).

Xiao Lan’s driving speed is always $1$, and the time for passengers to get on or off is ignored.

Determine the earliest time when Xiao Lan can complete all orders and finally return home.

Input Format

The first line contains two integers $n, m$, representing the number of east-west roads and the number of north-south roads.

The second line contains $n-1$ integers $h_{1}, h_{2}, \cdots, h_{n-1}$.

The third line contains $m-1$ integers $w_{1}, w_{2}, \cdots, w_{m-1}$.

The next $n$ lines each contain $m$ integers, describing the duration of the north-south green light at each intersection. The value in row $i$ and column $j$ is $g_{i j}$.

The next $n$ lines each contain $m$ integers, describing the duration of the east-west green light at each intersection. The value in row $i$ and column $j$ is $r_{i j}$.

The next line contains four integers $x_{1}, y_{1}, x_{2}, y_{2}$, meaning that Xiao Lan’s home is on the right side of the midpoint of the road segment between intersections $\left(x_{1}, y_{1}\right)$ and $\left(x_{2}, y_{2}\right)$.

The next line contains one integer $q$, representing the number of orders.

The next $q$ lines each describe an order. The $i$-th line contains eight integers $x_{i 1}, y_{i 1}, x_{i 2}, y_{i 2}$, $x_{i 3}, y_{i 3}, x_{i 4}, y_{i 4}$, meaning that the start of the $i$-th order is on the right side of the midpoint of the road segment between intersections $\left(x_{i 1}, y_{i 1}\right)$ and $\left(x_{i 2}, y_{i 2}\right)$, and the end of the $i$-th order is on the right side of the midpoint of the road segment between intersections $\left(x_{i 3}, y_{i 3}\right)$ and $\left(x_{i 4}, y_{i 4}\right)$.

Output Format

Output one real number, representing the earliest time when Xiao Lan finishes all orders and finally returns home. Round to one digit after the decimal point.

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

Hint

Sample Explanation

Xiao Lan has one order, and his driving route is shown in the figure below. Here $\mathrm{H}$ indicates the location of his home, $\mathrm{S}$ indicates the start point of the order, and $\mathrm{T}$ indicates the end point of the order. When returning home at the end, Xiao Lan needs to wait for the green light at an intersection where he wants to go straight. The waiting time is $20$.

Constraints and Assumptions

For $20\%$ of the testdata, $1 \leq n, m \leq 5, 1 \leq q \leq 10$.

For $50\%$ of the testdata, $1 \leq n, m \leq 30, 1 \leq q \leq 30$.

For all testdata, $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$. The given intersections are guaranteed to be valid.

Translated by ChatGPT 5