「Daily OI Round 3」City Planning

只要不失去你的崇高，整个世界都会为你敞开。

Provence-Alpes-Côte d'Azur 的管理者们遇上大麻烦了！他们邀请你来解决城市规划的问题。 这群管理者一共有 $t$ 人，并且这个地区一共有 $n$ 个城镇，第 $i$ 个城镇内部又有 $k_i$ 个村庄，通过 $p_i$ 条道路连接，第 $j$ 条道路双向连接第 $i$ 个城镇中的第 $u_{i,j}$ 和 $v_{i,j}$ 两个村庄，管理道路的人是第 $w_{i,j}$ 个，客流量是 $z_{i,j}$。 为了管理组内部的团结，保证每个人在同一个城镇最多管理 $1$ 条道路。 现在这些城镇中的村庄和村庄之间的道路都遭到了损坏，管理者们急于恢复这些城镇内的交通。这些城镇互相之间有 $m$ 条高铁，每条高铁连接了 $u,v$ 两个城镇，并且当初为了设计的优美，这 $n$ 个城镇和 $m$ 条高铁构成了一个**二分图**。 对于每个城镇 $i$，你都需要帮助管理组选择一个参数 $c_i(1 \le c_i \le k_i)$，修复一些村庄，编号在 $1 \sim c_i$ 之间的村庄都会被修复，如果道路的两端的村庄都修复了，那么这条道路就会自动修复。因此第 $i$ 个城镇中会产生 $b_{i,c_i}$ 的花费。 对于管理者 $i$ 来说，如果存在两条他在不同城镇管理的道路都没有被修复，并且这两条道路所属的城镇有高铁**直接连接**，你需要支付这两条道路的人流量的乘积来弥补损失，这样管理者 $i$ 才会高兴。（对于**任意**两条满足上述条件的道路你都需要弥补损失，而不是对于每个管理者只需要弥补一对道路的损失） 为了让管理组的成员都高兴并且给出的方案符合题目的要求（即 $1 \le c_i \le k_i$），你需要提前计算好自己至少需要支付多少钱以应对这一群管理者们的刁难。

第一行三个整数 $n,m,t$ 表示城镇的数量，城镇间的高铁的数量和管理组人员的数量。 接下来 $m$ 行每行两个整数 $x,y$ 表示这条高铁连接的两个城镇的编号。 接下来 $n$ 组输入，对于第 $i$ 组输入，格式如下： 第一行两个整数 $k_i,p_i$ 表示第 $i$ 个城镇有 $k_i$ 个村庄，$p_i$ 条道路。 第二行 $k_i$ 个整数，第 $j$ 个整数表示当 $c=j$ 时的花费 $b_{i,j}$。 接下来 $p_i$ 行，每行四个整数 $u_{i,j},v_{i,j},w_{i,j},z_{i,j}$，表示有一条边连接 $i$ 号城镇的第 $u_{i,j}$ 个村庄和第 $v_{i,j}$ 个村庄，并且管理道路的人是第 $w_{i,j}$ 个，客流量为 $z_{i,j}$。

一行一个整数表示让所有管理者都高兴的最小花费是多少。

2 2 3
2 1
2 1
1 3
3
1 1 2 3
1 1 1 1
1 1 3 3
2 0
7 6

9

3 1 3
1 2
3 2
1 2 3
1 2 1 3
2 3 2 2
2 2
1 100
1 1 1 3
1 2 2 1
5 1
5 0 5 5 5
4 5 1 3

4

5 6 5
4 3
3 5
1 2
2 1
3 4
3 5
2 0
37 44
4 2
33 2 43 49
3 1 3 6
3 4 4 6
6 4
4 23 0 9 35 22
3 4 2 7
3 4 5 3
2 1 3 2
4 4 4 10
3 2
14 41 35
2 2 4 1
3 3 2 5
3 5
27 39 9
3 3 2 1
3 2 3 3
2 1 1 5
2 1 5 3
1 2 4 8

71

#### 【样例解释 #1】 我们可以选择 $c_1=1,c_2=2$，那么花费就是 $b_{1,c_1}+b_{2,c_2}=3+6=9$，而没有一个管理员你需要讨好。 #### 【样例解释 #2】 我们可以选择 $c_1=1,c_2=1,c_3=2$，那么花费就是 $b_{1,c_1}+b_{2,c_2}+b_{3,c_3}=1+1=2$，但是管理员 $2$ 在城镇 $1$ 中管理的道路 $2 \to 3$ 不可能被修复，在城镇 $2$ 中管理的道路 $1 \to 2$ 不可能被修复，你就需要花费 $2 \times 1 = 2$ 的代价讨好管理员 $2$，总的代价就是 $4$。 你并不需要讨好管理员 $1$，哪怕他在城镇 $1$ 和 $3$ 中分别有一条道路不可能被修复，因为城镇 $1$ 和 $3$ 没有高铁相连，所以你不需要为此支付额外的资金。 #### 【数据范围】 对于全部数据保证：$1 \le n \le 50$，$1 \le k_i \le 100$，$0 \le p_i \le t$，$0 \le m \le 500$，$1 \le t \le 50$，$1 \le x,y \le n$，$x \ne y$，$0 \le b_{i,j} \le 10^9$，$1 \le u_{i,j},v_{i,j} \le k_i$，$1 \le w_{i,j} \le t$，$1 \le z_{i,j} \le 10^4$。 $n$ 个城镇和 $m$ 条高铁构成的图是一个二分图，每个管理员在同一个村庄管理的道路数量不超过 $1$。 **可能有连接同一对城镇的不同的高铁，不会出现自己连向自己的高铁。但城镇中的村庄可能会有自己连向自己的道路，也可能出现连接同一对村庄的不同的道路。**