B2. Доктор встречает Вейдера (средняя)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Благодаря помощи Доктора, повстанцам удалось украсть достаточно золота, чтобы запустить полномасштабную атаку на эмперию! Однако Дарт Вейдер ищет возможности отомстить и забрать назад своё золото.

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

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

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

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

У каждой базы есть местоположение $$$x$$$ и уровень защиты $$$d$$$.

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

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

Вейдер очень требователен к своим атакующим формациям. Он требует, чтобы каждый космический корабль атаковал не более одной базы, и чтобы каждая база была атакована не более чем одним космическим кораблем.

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

Таким образом, для каждой атакованной базы повстанцы теряют по $$$k$$$ золота.

Однако повстанцы имеют возможность создать произвольное количество фейковых баз. С помощью Доктора, эти базы будут существовать за пределами пространства и времени, так что все корабли смогут достичь и атаковать их. Более того, фейковые базы всегда будут казаться очень заманчивыми, то есть они гарантировано будут атакованы каким-то кораблём.

Разумеется, фейковые базы не содержат золота, но создание одной такой базы стоит $$$h$$$ золота.

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

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

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

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

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

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

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

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

Выведите одно целое число — минимальную цену в золоте.

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

Один из способов минимизировать стоимость — это построить $$$4$$$ фейковые базы, тем самым итоговая стоимость равна $$$4 \times 3 = 12$$$.

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