Deep Sea Specimen Collection Maximization

A submarine carrying several deep‐sea robots is about to begin a scientific expedition on the ocean floor. Once the submarine reaches the seabed, each robot will leave the submarine and move independently toward its predetermined destination.

On its way, each robot must collect marine biological specimens (each with a known value) located on the grid edges it traverses. However, each specimen can be collected only once – if more than one robot passes over an edge, only the robot that arrives there first will collect the specimen.

The robots are constrained to move only north or east. They operate on a $P\times Q$ grid, with the southwestern corner at $(0,0)$ and the northeastern corner at $(Q,P)$. A move east from $(x,y)$ to $(x+1,y)$ collects the specimen on the horizontal edge with value given in the input, and a move north from $(x,y)$ to $(x,y+1)$ collects the specimen on the vertical edge (its value also provided in the input).

You are given the grid dimensions, the values on all horizontal and vertical edges, and $R$ robots (each with a starting coordinate and a destination that satisfies $0\le sx \le tx\le Q$ and $0\le sy \le ty\le P$). Determine the maximum total value of specimens that can be collected if you choose an optimal monotonic (north–or–east only) path for each robot. All formulas are in LaTeX format.

inputFormat

The input is given as follows:

1. The first line contains three integers: $P$, $Q$, and $R$, where $P$ and $Q$ define the grid (the grid has $P$ rows and $Q$ columns) and $R$ is the number of robots.

2. The next $(P+1)$ lines each contain $Q$ integers. The $i$-th line (using 0–indexing for rows) contains the values on the horizontal edges in row $i$. An integer on this line corresponds to the edge from $(x,i)$ to $(x+1,i)$ for $0\le x<Q$.

3. The following $(Q+1)$ lines each contain $P$ integers. The $j$-th line contains the values on the vertical edges in column $j$. An integer on this line corresponds to the edge from $(j,y)$ to $(j,y+1)$ for $0\le y<P$.

4. The next $R$ lines each contain four integers: $sx$, $sy$, $tx$, $ty$, representing a robot's starting coordinate $(sx,sy)$ and its destination $(tx,ty)$ (with $0\le sx\le tx\le Q$ and $0\le sy\le ty\le P$).

outputFormat

Output a single integer – the maximum total value of specimens that can be collected by the robots along their chosen monotonic paths.

sample

2 2 1
1 2
3 4
5 6
7 8
9 10
11 12
0 0 2 2

26