Ride‐Hailing in Grid City

In the city of $L$, all roads are laid out in a grid: there are $n$ east–west roads $H_{1}, H_{2}, \dots, H_{n}$ (from north to south) and $m$ north–south roads $S_{1}, S_{2}, \dots, S_{m}$ (from west to east). Every east–west road is parallel to each other, and every north–south road is parallel to each other. In fact, every east–west road is perpendicular to every north–south road.

Intersections are denoted as $(i,j)$ where $H_{i}$ meets $S_{j}$. Starting at $(1,1)$, the intersections along the first east–west road occur at distances $w_{1}, w_{2}, \dots, w_{m-1}$ to the east, and along the first north–south road the intersections occur at distances $h_{1}, h_{2}, \dots, h_{n-1}$ to the south. (That is, the coordinate of intersection $(i,j)$ can be taken as ( (W_{j},H_{i}) ) with $$W_{j}=\sum_{k=1}^{j-1}w_{k},\quad H_{i}=\sum_{k=1}^{i-1}h_{k}.]\

Each intersection is controlled by a traffic light. At time $0$, the north–south green is on (and thus the east–west light is red). At each intersection $(i,j)$ the north–south green lasts for $g_{ij}$ time and the east–west green lasts for $r_{ij}$ time. The light changes instantaneously. When a car reaches an intersection:

• If the light in its travel direction is green, it may go straight, turn left, or turn right immediately. (If it arrives exactly at the moment when red turns to green, it is considered green.)
• If the light is red, the car may still make a right turn immediately but cannot go straight or turn left. (If it arrives exactly at the moment when green turns to red, it is considered red.)

Every road is bidirectional. However, there is a barrier in the middle of each road so that the car cannot change to the opposite lane (i.e. cannot make a U‐turn) except at intersections, where a U–turn is always allowed (with no extra delay regardless of the light). The car moves with a constant speed of $1$, and boarding/alighting take negligible time.

Xiao Lan starts at time $0$ from his home. He has $q$ ride orders to complete in sequence – he picks up a passenger at the order’s pickup location and then drops them off at the order’s drop–off location; he does no extra rides. After finishing all orders he returns home.

Both his home and the order pickup/drop–off locations are not at intersections but are located at the midpoint of a road segment (between two adjacent intersections). Each such location is described by two adjacent intersections: for example, a location is given by four integers $x_{1},y_{1},x_{2},y_{2}$ (guaranteed to be adjacent) to indicate the midpoint on the right side of the road from $(x_{1},y_{1})$ to $(x_{2},y_{2})$. Note that if the two intersections are swapped, it represents the midpoint on the opposite side of the same road – and because of the barrier the two midpoints are not immediately connected.

Xiao Lan drives only along the $n$ east–west and $m$ north–south roads and never leaves the rectangular area determined by $H_{1},H_{n},S_{1}$ and $S_{m}$.

Given the city configuration, the traffic light schedules at each intersection, the positions of Xiao Lan’s home, and the $q$ orders (each with a pickup and a drop–off location), compute the earliest time at which Xiao Lan can complete all orders and return home.

\textbf{Note on Modeling Simplification:} For this problem the detailed rules about turning and waiting at intersections (depending on the light) are simulated. In our intended solution the route planning is done via a state space search where every midpoint is connected to an associated intersection. In particular, every location (home or order midpoint) is attached to an intersection as follows. For a location given by two adjacent intersections:

• If the two intersections share the same row (i.e. the road is east–west), we define its associated intersection as $(x,\min(y_{1},y_{2}))$ and the cost to travel from the location to that intersection is half the east–west distance between them, namely $\frac{w_{\min(y_{1},y_{2})}}{2}$.
• If they share the same column (i.e. the road is north–south), its associated intersection is $(\min(x_{1},x_{2}),y)$ and the cost is half the north–south distance, i.e. $\frac{h_{\min(x_{1},x_{2})}}{2}$.

Furthermore, when traveling between any two such locations, one must add the cost to go from the source midpoint to its associated intersection, then the distance between intersections (using Manhattan distances computed from the given $h$ and $w$), and finally the cost from the destination intersection to the destination midpoint.

You may assume that test cases are designed so that waiting at traffic lights does not add extra delay (for example, by setting the green durations very long) and thus the problem reduces to careful computation of these distances.

\textbf{Input Format:} \begin{itemize} \item The first line contains two integers $n$ and $m$ ($2\le n,m\le 50$) --- the number of east–west and north–south roads respectively. \item The second line contains $n-1$ positive integers $h_{1},h_{2},\dots,h_{n-1}$, where $h_{i}$ is the distance between $H_{i}$ and $H_{i+1}$. \item The third line contains $m-1$ positive integers $w_{1},w_{2},\dots,w_{m-1}$, where $w_{j}$ is the distance between $S_{j}$ and $S_{j+1}$. \item Then follow $n$ lines, each containing $2\times m$ positive integers. In the $i$-th of these lines, the $2j-1$-th and $2j$-th numbers are $g_{ij}$ and $r_{ij}$ respectively, describing the traffic light at intersection $(i,j)$. (These values can be ignored in the simplified computation.) \item The next line contains four integers $x_{1}\; y_{1}\; x_{2}\; y_{2}$ describing Xiao Lan's home (which is the midpoint on the right side of the road between intersections $(x_{1},y_{1})$ and $(x_{2},y_{2}$); the two intersections are guaranteed to be adjacent). \item The next line contains an integer $q$ ($1\le q\le 100$) --- the number of orders. \item Then $q$ lines follow. Each order is given by 8 integers: $p_{1}\; p_{2}\; p_{3}\; p_{4}\; d_{1}\; d_{2}\; d_{3}\; d_{4}$, where the first four numbers describe the pickup location (the midpoint on the right side of the road between intersections $(p_{1},p_{2})$ and $(p_{3},p_{4})$) and the last four numbers describe the drop–off location in the same format. \end{itemize}

\textbf{Output Format:}

Output a number --- the earliest time (which may be fractional) that Xiao Lan can finish all orders and return home.

\textbf{Solution Outline (Simplified):}

For the purpose of this problem the following model is used. Associate with every midpoint a corresponding intersection and a half–segment cost as follows: \begin{itemize} \item If the two intersections share the same row (east–west road), let the associated intersection be $(x, \min(y_{1},y_{2}))$ and the cost be $\frac{w_{\min(y_{1},y_{2})}}{2}$. \item If they share the same column (north–south road), let the associated intersection be $(\min(x_{1},x_{2}), y)$ and the cost be $\frac{h_{\min(x_{1},x_{2})}}{2}$. \end{itemize}

Also, precompute the coordinates of intersections as

$$X_{j}=\sum_{k=1}^{j-1}w_{k},\quad Y_{i}=\sum_{k=1}^{i-1}h_{k}. $$

The Manhattan distance between intersections $(i,j)$ and $(p,q)$ is then (|Y_{i}-Y_{p}|+|X_{j}-X_{q}|).

Define the cost of traveling between two midpoints $A$ and $B$ (with associated intersections $A_I$ and $B_I$, and respective half–costs $c_A$ and $c_B$) as:

$$cost(A,B)=c_A+\text{Manhattan}(A_I,B_I)+c_B.$$

The answer is the sum over the route:

Home ( \to ) Order 1 pickup ( \to ) Order 1 drop ( \to ) Order 2 pickup ( \to ) Order 2 drop ( \to ) ... ( \to ) Home.

For example, consider the following test case.

\textbf{Sample Input 1:} \begin{verbatim} 2 2 10 20 1000 1 1000 1 1000 1 1000 1 1 1 1 2 1 2 1 2 2 1 1 1 2 \end{verbatim}

For the home location given by “1 1 1 2” (an east–west road), the associated intersection is $(1,1)$ and the half–cost is $20/2=10$.

For the order, the pickup location is given by “2 1 2 2” (associated with $(2,1)$ with half–cost $10$) and the drop–off is given by “1 1 1 2$” (associated with$(1,1)$ with half–cost $10$).

Then the total route cost is computed as: [ \underbrace{10+;,;;10; +10}{\text{home to pickup}} + \underbrace{10+10+10}{\text{pickup to drop}} + \underbrace{10+0+10}_{\text{drop to home}} = 80. ]

\textbf{Sample Output 1:} 80

Note that although the traffic light details are given, the test data is designed so that waiting does not occur.

inputFormat

The input begins with two integers n and m.

1. Line 1: Two integers n m ($2 \le n,m \le 50$).
2. Line 2: n-1 integers: h1 h2 ... hn-1.
3. Line 3: m-1 integers: w1 w2 ... wm-1.
4. Next n lines: each line contains 2*m integers. In the i-th line, the numbers represent gi1 ri1 gi2 ri2 ... gim rim.
5. Next line: Four integers x1 y1 x2 y2 describing Xiao Lan’s home (midpoint on the right side of the road between intersections (x1,y1) and (x2,y2)).
6. Next line: An integer q --- the number of orders.
7. Then q lines follow, each containing 8 integers: p1 p2 p3 p4 d1 d2 d3 d4, where
   • p1 p2 p3 p4 describe the pickup midpoint (from intersections (p1,p2) and (p3,p4)), and
   • d1 d2 d3 d4 describe the drop–off midpoint (from intersections (d1,d2) and (d3,d4)).

outputFormat

Output a single number representing the earliest time (possibly fractional) at which Xiao Lan can complete all orders and return home.

sample

2 2
10
20
1000 1 1000 1
1000 1 1000 1
1 1 1 2
1
2 1 2 2 1 1 1 2

80