题目描述

给定一个平面上 $\red n$ 条水平直线和 $\red m$ 条垂直直线，它们相交形成 $\red n$行$\red m$ 列的网格，从上到下第 $\red r$ 条水平直线和从左到右第 $\red c$ 条垂直直线之间的交点称为格点 ($\red {r,c}$)。

网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。

进行 $\red T$ 次询问，每次询问形式如下：

给出 $\red k$（$\red T$ 次询问的 $\red k$ 可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。

所有从网格边缘向外出发的射线按左上 - 右上 - 右下 - 左下 - 左上的顺序依次编号为 $\red 1$ 到 $\red {2n+2m}$，如下图：

对于每次询问，不同附加点所在的射线互不相同。

每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。

给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。

请输出这个最小的边权和。

输入格式

第一行，三个正整数 $\red n$,$\red m$,$\red T$，分别表示水平、垂直直线的数量，以及询问次数。

接下来 $\red {n−1}$行，每行 $\red m$ 个非负整数。

其中第 $\red i$ 行的第 $\red j$ 个非负整数 $\red {x1_{i,j}}$ 表示 ($\red {i,j}$) 和 ($\red {i+1,j}$) 间的边权。

接下来 $\red n$ 行，每行 $\red {m−1}$ 个非负整数。

其中第 $\red i$ 行的第 $\red j$ 个非负整数 $\red {x2_{i,j}}$ 表示 ($\red {i,j}$) 和 ($\red {i,j+1}$) 间的边权。

接下来依次输入 $\red T$ 组询问。

第 $\red i$ 组询问开头为一行一个正整数 $\red {k_i}$ 表示这次询问附加点的总数。

接下来 $\red {k_i}$行每行三个非负整数。

其中第 $\red j$ 行依次为 $\red {x3_{i,j},p_{i,j},t_{i,j}}$ 表示第 $\red j$ 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（$\red 0$ 为白色，$\red 1$ 为黑色）。

保证同一组询问内 $\red {p_{i,j}}$ 互不相同。

每行的多个整数由空格分隔。

输出格式

输出 $\red T$ 行，第 $\red i$ 行输出一个非负整数，表示第 $\red i$ 次询问染色之后两端颜色不同的边权和的最小值。

输入输出样例

输入样例1

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

输出样例1

12

说明/提示

样例解释

最优方案：($\red {1,3}$),($\red {1,2}$),($\red {2,3}$)为黑色；($\red {1,1}$),($\red {2,1}$),($\red {2,2}$) 为白色。

【数据范围】

测试点编号	$\red {n,m ≤}$	$\red {k_i≤}$
$\red {1∼2 }$	$\red { 5 }$	$\red { 50}$
$\red {3∼5 }$	$\red { 18 }$	$\red { 2 }$
$\red {6∼8 }$		$\red { 50}$
$\red {9∼10 }$	$\red { 100}$	$\red { 2 }$
$\red {11∼12}$		$\red { 50}$
$\red {13∼16}$	$\red { 500}$	$\red { 2 }$
$\red {17∼20}$		$\red { 50}$

对于所有数据，$\red {2≤n,m≤500}$，$\red {1≤T≤50}$，$\red {1≤k_i ≤ min⁡\{2(n+m),50\}}$，$\red {1≤ \sum _{i=1}^{T} k_i≤50}$ ，$\red {0≤x≤10^6}$，$\red {1≤p≤2(n+m)}$，$\red {t∈\{0,1\} }$。

保证对于每个 $\red {i∈[1,T]，p_{i,j}}$ 互不相同。