29511번 - Железнодорожные перевозки 다국어

문제

У Антона очень много денег. Поэтому он хочет купить Небольшую Железнодорожную Компанию (НЖК). Однако перед тем как купить ее, Антон хочет знать, какую максимальную прибыль компания может приносить.

Рассмотрим подробнее сеть железных дорог. Он состоит из $n$ узловых станций, которые соединены $m$ перегонами. По перегону можно совершать перевозки в обоих направлениях. Железные дороги и локомотивы компании имеют высокое качество, поэтому по дорогам можно очень быстро и бесплатно провозить любое количество товаров.

НЖК в состоянии перевозить по своим путям $k$ различных видом товаров. Рядом со станциями бывают объекты трех видов:

1. Добывающие предприятия. На них происходит добыча некоторого товара, например древесины. Антон знает про каждое такое предприятие, какое количество товара в год оно может произвести. Количество товара измеряется в вагонах. Товар на добывающих предприятиях ничего не стоит, так как Антон уже давно их все купил.
2. Перерабатывающие предприятия. На них происходит переработка одного вида товара в другой, например из древесины могут получатся отличные квадратные столы. Про каждое предприятие такого типа известно сколько в год оно может переработать товара. При переработке количество товара сохраняется, например за вагон древесины перерабатывающее предприятие выдает вагон квадратных столов. Переработка товаров также ничего не стоит, так и этими предприятиями владеет Антон.
3. Города. Города потребляют различные товары. Про каждый город известно сколько и каких товаров в год ему нужно. Продавая городу один вагон необходимого товара Антон зарабатывает один наномиллиард условных денег. Предоставление городу товаров сверх нормы прибыль не приносит.

Антона очень просит Вас написать программу, которая определяла бы максимальную прибыль, которую НЖК может приносить за год.

입력

В первой строке входного файла три целых числа $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$) --- номер товара, который добывает предприятие, и максимальное количество добываемого товара в год.

В следующей строке блока содержится целое число $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$) --- номер товара, который предприятие получает на переработку, номер товара, получающегося в процессе переработки, и максимальное количество перерабатываемого товара в год.

В следующей строке блока содержится целое число $c$ --- число товаров, потребляемых городом. Далее идут $c$ строк по два целых числа $g$ и $a$ (1ドル \le g \le k,ドル 1ドル \le a \le 10^9$) --- номер товара, который потребляет город, и максимальное количество потребляемого товара в год.

Количество товара всегда измеряется в вагонах. Гарантируется, что сумма всех $r,ドル $p$ и $c$ не превысит 50000ドル$.

출력

В выходной файл выведите единственное число --- максимальная возможная прибыль компании в наномиллиардах.

제한

힌트