Background

As long as you do not lose your nobility, the whole world will open up to you.

Problem Description

The administrators of Provence-Alpes-Côte d'Azur have run into big trouble. They invited you to solve a city planning problem.

There are $t$ administrators in total, and there are $n$ towns in this region. In town $i$, there are $k_i$ villages, connected by $p_i$ roads. The $j$-th road bidirectionally connects villages $u_{i,j}$ and $v_{i,j}$ in town $i$. The person in charge of this road is administrator $w_{i,j}$, and the passenger flow is $z_{i,j}$.

To maintain unity within the administrator group, each person can manage at most $1$ road in the same town.

Now, the villages and the roads between villages in these towns have all been damaged, and the administrators urgently want to restore transportation inside these towns. Between the towns, there are $m$ high-speed railways. Each railway connects two towns $u, v$. Also, for aesthetic design reasons, the $n$ towns and the $m$ high-speed railways form a bipartite graph.

For each town $i$, you need to help the administrator group choose a parameter $c_i(1 \le c_i \le k_i)$ and repair some villages. All villages with indices in $1 \sim c_i$ will be repaired. If both endpoints of a road are repaired, then the road will be repaired automatically. Therefore, in town $i$, a cost of $b_{i,c_i}$ will be incurred.

For administrator $i$, if there exist two roads managed by them in different towns that are both not repaired, and the towns these two roads belong to are directly connected by a high-speed railway, then you need to pay the product of the passenger flows of these two roads to compensate for the loss, so that administrator $i$ will be satisfied. (For any pair of roads that satisfies the above conditions, you must compensate for the loss, not just compensate for one pair per administrator.)

To make all members of the administrator group satisfied and ensure that the plan meets the requirements of the problem (i.e., $1 \le c_i \le k_i$), you need to compute in advance the minimum amount of money you have to pay to deal with these administrators' demands.

Input Format

The first line contains three integers $n, m, t$, representing the number of towns, the number of high-speed railways between towns, and the number of administrators.

The next $m$ lines each contain two integers $x, y$, indicating that this high-speed railway connects towns $x$ and $y$.

Then follow $n$ groups of input. For the $i$-th group, the format is as follows:

The first line contains two integers $k_i, p_i$, indicating that town $i$ has $k_i$ villages and $p_i$ roads.

The second line contains $k_i$ integers. The $j$-th integer represents the cost $b_{i,j}$ when $c = j$.

The next $p_i$ lines each contain four integers $u_{i,j}, v_{i,j}, w_{i,j}, z_{i,j}$, indicating that there is an edge connecting the $u_{i,j}$-th village and the $v_{i,j}$-th village in town $i$, the person in charge is administrator $w_{i,j}$, and the passenger flow is $z_{i,j}$.

Output Format

Output one integer in one line, representing the minimum total cost to make all administrators satisfied.

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

Hint

Sample Explanation #1

We can choose $c_1 = 1, c_2 = 2$. Then the cost is $b_{1,c_1} + b_{2,c_2} = 3 + 6 = 9$, and there is no administrator that you need to compensate.

Sample Explanation #2

We can choose $c_1 = 1, c_2 = 1, c_3 = 2$. Then the cost is $b_{1,c_1} + b_{2,c_2} + b_{3,c_3} = 1 + 1 = 2$. However, administrator $2$'s road $2 \to 3$ in town $1$ cannot possibly be repaired, and their road $1 \to 2$ in town $2$ cannot possibly be repaired either, so you need to pay $2 \times 1 = 2$ to compensate administrator $2$. The total cost is $4$.

You do not need to compensate administrator $1$, even though they have one road in town $1$ and one road in town $3\,$ that cannot be repaired, because towns $1$ and $3$ are not connected by a high-speed railway, so you do not need to pay extra money for this.

Constraints

For all data, it is guaranteed that: $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$.

The graph formed by the $n$ towns and the $m$ high-speed railways is a bipartite graph. For each administrator, the number of roads they manage within the same village does not exceed $1$.

There may be multiple different high-speed railways connecting the same pair of towns, and there will be no railway that connects a town to itself. However, within a town, villages may have roads that connect to themselves, and there may also be multiple different roads connecting the same pair of villages.

Translated by ChatGPT 5