Благодаря помощи Доктора, повстанцам удалось украсть достаточно золота, чтобы запустить полномасштабную атаку на эмперию! Однако Дарт Вейдер ищет возможности отомстить и забрать назад своё золото.
Повстанцы спрятали золото на различных базах по всей галактике. Дарт Вейдер и Империя собираются послать свои космические корабли в атаку на эти базы.
Галактика может быть представлена как неориентированный граф из $$$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$$$.
По одному имперскому кораблю будет назначено на атаку каждой фейковой базы, тем самым будет атаковано ноль настоящих баз.
Название |
---|