Railway Transport

Anton has a lot of money, so he wants to buy a small railway company (NZhK). Before buying it, he wants to know the maximum profit the company can make.

Consider the railway network. It consists of $n$ junction stations connected by $m$ track segments. Trains can run in both directions along each segment. The company's tracks and locomotives are of high quality, so any amount of goods can be carried along the tracks very quickly and at no cost.

The company can carry $k$ different kinds of goods. Next to the stations there are three types of facilities:

1. Mining enterprises. Each one produces a certain kind of goods, for example timber. For each one, Anton knows how many wagons of goods it can produce per year. Goods at mining enterprises cost nothing, since Anton has already bought all of them.
2. Processing enterprises. Each one converts one kind of goods into another, for example timber into fine wooden tables. For each one, Anton knows how much goods it can process per year. The amount is preserved: one wagon of timber becomes one wagon of tables. Processing is free as well, since Anton owns these enterprises too.
3. Cities. Cities consume various goods. For each city, Anton knows which goods it needs and how much per year. Each wagon of a needed good sold to a city earns Anton one nanomilliard of money. Supplying a city beyond its needs earns no extra profit.

Write a program that finds the maximum profit the company can earn in one year.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 100$, $0 \le m \le 5000$, $1 \le k \le 10$). The next $m$ lines each contain two numbers, the stations connected by a track segment. After that come $n$ blocks describing the facilities next to each station.

The first line of a block contains $r$, the number of mining enterprises. The next $r$ lines each contain two integers $g$ and $a$ ($1 \le g \le k$, $1 \le a \le 10^9$): the kind of goods mined and the maximum amount mined per year, in wagons.

The next line contains $p$, the number of processing enterprises. The next $p$ lines each contain three integers $g_1$, $g_2$, and $a$ ($1 \le g_1, g_2 \le k$, $g_1 \neq g_2$, $1 \le a \le 10^9$): the kind of goods received for processing, the kind of goods produced, and the maximum amount processed per year.

The next line contains $c$, the number of goods consumed by the city. The next $c$ lines each contain two integers $g$ and $a$ ($1 \le g \le k$, $1 \le a \le 10^9$): the kind of goods consumed and the maximum amount consumed per year.

Goods are always measured in wagons. It is guaranteed that the sum of all $r$, $p$, and $c$ does not exceed 50000.

Print a single number: the maximum possible profit of the company in nanomilliards.