[CSP2021]交通规划（traffic）
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个平面上n条水平直线和m条垂直直线，它们相交形成n行m列的网格， 从上到下第r条水平直线和从左到右第c条垂直直线之间的交点称为格点(r, c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。

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

给出k（T次询问的k可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依  次编号为1到，如下图：

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

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

输入描述:

第一行3个正整数n, m ,T分别表示水平、垂直直线的数量，以及询问次数。
接下来行，每行m个非负整数。其中第i行的第j个非负整数表示(i, j)和间的边权。
接下来n行，每行个非负整数。其中第i行的第j个非负整数表示(i, j)和间的边权。
接下来依次输入T组询问。第i组询问开头为一行一个正整数k_i表示这次询问附加点的总数。接下来k_i行每行三个非负整数。其中第j行依次为表示第i个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（0 为白色，1 为黑色）。保证同一组询问内互不相同。
每行的多个整数由空格分隔。

输出描述:

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

输入

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

输出

复制 
12

说明

最优方案：(1,3),(1,2),(2,3) 为黑色；(1,1),(2,1),(2,2) 为白色。

备注:

对于所有数据,  。
保证对于每个，互不相同。