B3. Доктор встречает Вейдера (сложная)
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Повстанцы сохранили достаточно золота, чтобы подготовить полномасштабную атаку. Теперь ситуация перевернулась и повстанцы запускают космические корабли, чтобы атаковать базы Империи!

Галактика может быть представлена как неориентированый граф из $$$n$$$ планет (вершин) и $$$m$$$ червоточин (рёбра), каждая из которых соединяет две планеты.

Всего есть $$$s$$$ космических кораблей повстанцев и $$$b$$$ баз Империи, расположеных на различных планетах галактики.

Каждый космический корабль имеет местоположение $$$x$$$, обозначающее индекс планеты, на которой он расположен, силу атаки $$$a$$$, определённый уровень энергии $$$f$$$ и цена эксплуатации $$$p$$$.

Каждая база имеет местоположение $$$x$$$, силу защиты $$$d$$$ и определённый уровень золота $$$g$$$.

Космический корабль может атаковать базу, если выполняются оба следующих условия:

  • Сила атаки космического корабля больше или равна силе защиты базы
  • Уровень топлива космического корабля больше или равен кратчайшему расстоянию (количеству червоточин) между планетой космического корабля и планетой, на которой расположена база.

Повстанцы очень гордые бойцы. Например, если космический корабль не может атаковать ни одну базу, ни один пилот повстанцев не согласится управлять им.

Если космический корабль управляется, то прибыль, которую производит этот корабль, равна золоту базы, которую он атакует, минус цену за эксплуатацию этого корабля. Обратите внимание, что эта величина может быть отрицательной. Пилот корабля выберет ту базу для атаки, которая максимизирует полученную прибыль.

Дарт Вейдер любит казаться богатым. Поэтому всякий раз, когда база подвергается нападению, он немедленно пополняет эту базу новым золотом, вместо похищенного.

Тем самым, с точки зрения повстанцев, разные корабли могут свободно атаковать одну и ту же базу, в таком случае все атакующие получат золото от этой базы.

Повстанцы попросили Хайди и Доктора определить какой набор кораблей следует использовать, чтобы получить максимальную суммарную прибыль.

Однако, так как война продолжалась достаточно долго времени, то между пилотами возникли различные нерушимые связи, и некоторые из них отказываются управлять кораблём, если их друзья не управляют своими кораблями.

В частности есть список из $$$k$$$ зависимостей вида $$$s_1, s_2$$$, обозначающие, что корабль $$$s_1$$$ можно использовать только если корабль $$$s_2$$$ тоже используется.

Входные данные

Первая строка содержит целые числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 100$$$, $$$0 \leq m \leq 10000$$$) — количество вершин и количество рёбер.

Следующие $$$m$$$ строк содержат целые числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$), обозначающие неориентированное ребро между двумя вершинами.

Следующая строка содержит целые числа $$$s$$$, $$$b$$$ и $$$k$$$ ($$$1 \leq s, b \leq 10^5$$$, $$$0 \leq k \leq 1000$$$) — количество космических кораблей, баз и зависимостей.

Следующие $$$s$$$ строк содержат целые числа $$$x, a, f, p$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq a, f, p \leq 10^9$$$) — местоположение, сила атаки, уровень топлива и цену эксплуатации корабля. Корабли пронумерованы от $$$1$$$ до $$$s$$$.

Следующие $$$b$$$ строк содержат целые числа $$$x, d, g$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq d, g \leq 10^9$$$) — обозначающие местоположение, уровень защиты и количество золота на базе.

Следующие $$$k$$$ строк содержат целые числа $$$s_1$$$ и $$$s_2$$$ ($$$1 \leq s_1, s_2 \leq s$$$), обозначающие зависимость $$$s_1$$$ от $$$s_2$$$.

Выходные данные

Выведите одно целое число — максимальную суммарную прибыль, которую можно получить.

Пример
Входные данные
6 7
1 2
2 3
3 4
4 6
6 5
4 4
3 6
4 2 2
1 10 2 5
3 8 2 7
5 1 0 2
6 5 4 1
3 7 6
5 2 3
4 2
3 2
Выходные данные
2
Примечание

Оптимальной стратегией является выбрать корабли 1, 2, and 4, которые будут атаковать базы 1, 1 и 2 соответственно.