Problem Background

As long as you do not lose your noble aspirations, the entire world will open its doors to you.

Problem Description

The managers of Provence-Alpes-Côte d'Azur are in big trouble! They have invited you to solve the city planning issues.

There are $t$ managers in total, and the region consists of $n$ towns. The $i$-th town has $k_i$ villages connected by $p_i$ roads. The $j$-th road in town $i$ connects villages $u_{i,j}$ and $v_{i,j}$ bidirectionally, managed by the $w_{i,j}$-th manager, with a traffic flow of $z_{i,j}$.

To maintain unity within the management group, each manager is allowed to manage at most one road in each town.

Currently, the roads between villages in these towns are damaged, and the managers are eager to restore the internal traffic. There are $m$ high-speed trains connecting towns $u$ and $v$, and the $n$ towns and $m$ high-speed trains form a bipartite graph.

For each town $i$, you need to help the management group select a parameter $c_i$ (where $1 \le c_i \le k_i$), which determines the number of villages to be repaired. Villages numbered from $1$ to $c_i$ will be repaired. If both ends of a road are repaired, the road will automatically be restored, resulting in a cost of $b_{i,c_i}$ in town $i$.

For manager $i$, if there are two roads they manage in different towns that are not repaired, and these towns are directly connected by a high-speed train, you need to pay the product of the traffic flows of these two roads to compensate for the loss, making manager $i$ happy. (You need to compensate for any pair of roads that meet the above conditions, not just one pair per manager.)

To ensure all managers are happy and the solution meets the problem's requirements (i.e., $1 \le c_i \le k_i$), you need to calculate the minimum amount you need to pay to handle the managers' demands.

Input Format

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

The next $m$ lines each contain two integers $x$ and $y$, indicating that there is a high-speed train connecting towns $x$ and $y$.

The following $n$ groups of inputs describe each town $i$:

• The first line contains two integers $k_i$ and $p_i$, representing the number of villages and roads in town $i$, respectively.
• The second line contains $k_i$ integers, where 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}$, and $z_{i,j}$, indicating a road connecting villages $u_{i,j}$ and $v_{i,j}$ in town $i$, managed by the $w_{i,j}$-th manager, with a traffic flow of $z_{i,j}$.

Output Format

A single integer representing the minimum cost to make all managers happy.

Sample Input and Output

Input Sample #1

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

Output Sample #1

9

Input Sample #2

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

Output Sample #2

4

Input Sample #3

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

Output Sample #3

71

Notes/Hints

Sample Explanation #1

We can choose $c_1 = 1$ and $c_2 = 2$, resulting in a cost of $b_{1,c_1} + b_{2,c_2} = 3 + 6 = 9$, and no manager needs to be appeased.

Sample Explanation #2

We can choose $c_1 = 1$, $c_2 = 1$, and $c_3 = 2$, resulting in a cost of $b_{1,c_1} + b_{2,c_2} + b_{3,c_3} = 1 + 1 + 2 = 4$. However, manager $2$ has roads in towns $1$ and $2$ that cannot be repaired, requiring a payment of $2 \times 1 = 2$, making the total cost $4$.

You do not need to appease manager $1$ even though they have unrepairable roads in towns $1$ and $3$, as these towns are not connected by a high-speed train, so no additional payment is needed.

Data Range

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 $n$ towns and $m$ high-speed trains is a bipartite graph, and each manager manages at most one road in the same village.

There may be multiple high-speed trains connecting the same pair of towns, but no high-speed train connects a town to itself. However, towns may have roads connecting a village to itself, or multiple roads connecting the same pair of villages.

见题面 Input 部分

见题面 Output 部分