철도 운송

안톤은 돈이 아주 많다. 그래서 소규모 철도 회사(NZhK)를 사려고 한다. 사기 전에 이 회사가 1년 동안 낼 수 있는 최대 이익을 알고 싶어 한다.

철도망을 살펴보자. 철도망은 $n$개의 거점 역으로 이루어지며, 이 역들은 $m$개의 구간으로 연결되어 있다. 각 구간은 양방향으로 운행할 수 있다. 회사의 선로와 기관차는 품질이 높아서, 선로를 따라 원하는 양만큼의 화물을 매우 빠르고 무료로 운송한다.

회사는 $k$종류의 서로 다른 화물을 운송할 수 있다. 역 주변에는 세 종류의 시설이 있다.

1. 채굴 시설. 각 시설은 특정 화물을 생산한다. 예를 들어 목재가 있다. 안톤은 각 시설이 1년에 생산할 수 있는 화물의 양을 차량 단위로 알고 있다. 채굴 시설의 화물은 안톤이 이미 모두 구입했으므로 비용이 들지 않는다.
2. 가공 시설. 각 시설은 한 종류의 화물을 다른 종류로 바꾼다. 예를 들어 목재를 고급 나무 탁자로 만든다. 안톤은 각 시설이 1년에 가공할 수 있는 양을 알고 있다. 가공해도 양은 그대로 유지된다. 목재 1차량이 탁자 1차량이 된다. 이 시설도 안톤이 소유하고 있으므로 가공 비용은 들지 않는다.
3. 도시. 도시는 여러 화물을 소비한다. 안톤은 각 도시가 1년에 필요로 하는 화물과 그 양을 알고 있다. 도시에 필요한 화물을 1차량 팔 때마다 안톤은 1나노밀리아르드를 번다. 필요량을 넘어서 공급해도 이익은 늘지 않는다.

회사가 1년 동안 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하라.

첫 줄에 세 정수 $n$, $m$, $k$($1 \le n \le 100$, $0 \le m \le 5000$, $1 \le k \le 10$)가 주어진다. 이어서 $m$개의 줄에 구간이 잇는 두 역의 번호가 주어진다. 그 다음에는 각 역 주변의 시설을 설명하는 $n$개의 블록이 나온다.

블록의 첫 줄에는 채굴 시설의 수 $r$이 주어진다. 이어지는 $r$개의 줄에는 정수 $g$와 $a$($1 \le g \le k$, $1 \le a \le 10^9$)가 주어진다. $g$는 채굴하는 화물의 번호이고, $a$는 1년에 채굴할 수 있는 최대량(차량 단위)이다.

다음 줄에는 가공 시설의 수 $p$가 주어진다. 이어지는 $p$개의 줄에는 정수 $g_1$, $g_2$, $a$($1 \le g_1, g_2 \le k$, $g_1 \neq g_2$, $1 \le a \le 10^9$)가 주어진다. $g_1$은 가공을 위해 받는 화물의 번호, $g_2$는 가공 결과로 나오는 화물의 번호, $a$는 1년에 가공할 수 있는 최대량이다.

다음 줄에는 도시가 소비하는 화물의 수 $c$가 주어진다. 이어지는 $c$개의 줄에는 정수 $g$와 $a$($1 \le g \le k$, $1 \le a \le 10^9$)가 주어진다. $g$는 도시가 소비하는 화물의 번호이고, $a$는 1년에 소비하는 최대량이다.

화물의 양은 항상 차량 단위로 측정한다. 모든 $r$, $p$, $c$의 합은 50000을 넘지 않는다고 보장된다.

최대 이익을 나노밀리아르드 단위로 나타내는 정수 하나를 출력한다.