Person in Charge

• SleepingCup

Problem Description

Given $n$ horizontal lines and $m$ vertical lines on a plane, they intersect to form a grid with $n$ rows and $m$ columns. The intersection of the $r$-th horizontal line from the top and the $c$-th vertical line from the left is called the grid point $(r, c)$. A line segment between any two horizontally or vertically adjacent grid points in the grid is called an edge, and each edge has a non-negative integer weight.

We perform $T$ queries, each in the following form:

Given $k$ (the value of $k$ may vary across $T$ queries) additional points, each lying on a ray starting outward from the grid boundary. All such rays starting outward from the grid boundary are numbered from $1$ to $2n+2m$ in the order of $\text{upper left} \to \text{upper right} \to \text{lower right} \to \text{lower left} \to \text{upper left}$, as shown in the figure below:

An image is available here. If not visible, download it from the "Attachments" section.

For each query, the rays where different additional points lie are pairwise distinct. The line segment between each additional point and the nearest grid point is also defined as an edge with a non-negative integer weight (note that a grid point at a corner may be connected to two additional points simultaneously).

Each additional point is assigned a color (black or white). You need to color each grid point in the grid either black or white such that the sum of the weights of all edges whose two endpoints have different colors is minimized. Output this minimal sum of weights.

Input Format

The first line contains three positive integers $n, m, T$, representing the number of horizontal lines, vertical lines and queries respectively.

The next $n-1$ lines each contain $m$ non-negative integers. The $j$-th non-negative integer ${x1}_{i,j}$ in the $i$-th line denotes the weight of the edge between $(i,j)$ and $(i+1,j)$.

The next $n$ lines each contain $m-1$ non-negative integers. The $j$-th non-negative integer ${x2}_{i,j}$ in the $i$-th line denotes the weight of the edge between $(i,j)$ and $(i,j+1)$.

Then $T$ groups of queries follow in sequence. The start of the $i$-th group of queries is a line with a positive integer $k_i$, representing the total number of additional points for this query. The next $k_i$ lines each contain three non-negative integers, where the $j$-th line has ${x3}_{i,j}, p_{i,j}, t_{i,j}$ in turn, denoting the weight of the edge between the $j$-th additional point and its adjacent grid point, the ray number where the additional point lies, and the color of the additional point ($0$ for white, $1$ for black). It is guaranteed that all $p_{i,j}$ in the same query are distinct.

Multiple integers in each line are separated by spaces.

Output Format

Output $T$ lines, where the $i$-th line contains a non-negative integer representing the minimal sum of the weights of edges with different colored endpoints after coloring for the $i$-th query.

Samples

2 3 1
9 4 7
3 8
10 5
2
19 3 1
17 9 0

12

Sample (1) Explanation

The optimal coloring scheme: $(1, 3), (1, 2), (2, 3)$ are black; $(1, 1), (2, 1), (2, 2)$ are white.

Sample (2)

See traffic/traffic2.in and traffic/traffic2.ans in the contestant's directory.

Sample (3)

See traffic/traffic3.in and traffic/traffic3.ans in the contestant's directory.

Sample (4)

See traffic/traffic4.in and traffic/traffic4.ans in the contestant's directory.

Sample (5)

See traffic/traffic5.in and traffic/traffic5.ans in the contestant's directory.

Data Range

For all test data, $2 \le n, m \le 500$, $1 \le T \le 50$, $1 \le k_i \le \min \{ 2 (n + m), 50 \}$, $1 \le \sum_{i = 1}^{T} k_i \le 50$, $0 \le x \le 10^6$, $1 \le p \le 2 (n + m)$, $t \in \{ 0, 1 \}$.

It is guaranteed that for each $i \in [1, T]$, all $p_{i,j}$ are distinct.