CF1184B2.The Doctor Meets Vader (Medium)

Thanks to the Doctor's help, the rebels managed to steal enough gold to launch a full-scale attack on the Empire! However, Darth Vader is looking for revenge and wants to take back his gold.

The rebels have hidden the gold in various bases throughout the galaxy. Darth Vader and the Empire are looking to send out their spaceships to attack these bases.

The galaxy can be represented as an undirected graph with $n$ planets (nodes) and $m$ wormholes (edges), each connecting two planets.

A total of $s$ empire spaceships and $b$ rebel bases are located at different planets in the galaxy.

Each spaceship is given a location $x$, denoting the index of the planet on which it is located, an attacking strength $a$, and a certain amount of fuel $f$.

Each base is given a location $x$, and a defensive strength $d$.

A spaceship can attack a base if both of these conditions hold:

• the spaceship's attacking strength is greater or equal than the defensive strength of the base
• the spaceship's fuel is greater or equal to the shortest distance, computed as the number of wormholes, between the spaceship's planet and the base's planet

Vader is very particular about his attacking formations. He requires that each spaceship is to attack at most one base and that each base is to be attacked by at most one spaceship.

Vader knows that the rebels have hidden $k$ gold in each base, so he will assign the spaceships to attack bases in such a way that maximizes the number of bases attacked.

Therefore, for each base that is attacked, the rebels lose $k$ gold.

However, the rebels have the ability to create any number of dummy bases. With the Doctor's help, these bases would exist beyond space and time, so all spaceship can reach them and attack them. Moreover, a dummy base is designed to seem irresistible: that is, it will always be attacked by some spaceship.

Of course, dummy bases do not contain any gold, but creating such a dummy base costs $h$ gold.

What is the minimum gold the rebels can lose if they create an optimal number of dummy bases?

在博士的帮助下，反抗军成功窃取了足够多的黄金，得以对银河帝国发动全面进攻！然而，达斯·维达渴望复仇，想要夺回属于他的黄金。

反抗军已将黄金藏匿于银河系各处的多个基地中。达斯·维达与帝国正计划派出宇宙飞船攻击这些基地。

整个银河系可建模为一个无向图，包含 $n$ 颗行星（节点）和 $m$ 个虫洞（边），每条边连接两颗行星。

共有 $s$ 艘帝国飞船和 $b$ 座反抗军基地，分别位于银河系中不同的行星上。

每艘飞船具有以下属性：位置 $x$（表示其所在行星的编号）、攻击力 $a$、以及燃料量 $f$。

每座基地具有以下属性：位置 $x$（表示其所在行星的编号）、防御力 $d$。

一艘飞船能够攻击一座基地，当且仅当同时满足以下两个条件：

• 该飞船的攻击力不小于该基地的防御力；
• 该飞船的燃料量不小于该飞船所在行星与该基地所在行星之间的最短距离（以虫洞数量计）。

维达对进攻阵型极为讲究：他要求每艘飞船最多攻击一座基地，且每座基地最多被一艘飞船攻击。

维达知道反抗军在每座基地中藏匿了 $k$ 单位黄金，因此他将指派飞船攻击基地，以最大化被攻击的基地数量。

于是，每座被攻击的基地，反抗军都将损失 $k$ 单位黄金。

然而，反抗军有能力建造任意数量的诱饵基地（dummy bases）。在博士的帮助下，这些诱饵基地存在于时空之外，因此所有飞船均可抵达并攻击它们。此外，诱饵基地被设计得极具吸引力：即总会被某艘飞船攻击。

当然，诱饵基地中不含任何黄金，但每建造一座诱饵基地需耗费 $h$ 单位黄金。

若反抗军建造最优数量的诱饵基地，他们所能承受的最小黄金损失是多少？

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 100$, $0 \leq m \leq 10000$), the number of nodes and the number of edges, respectively.

The next $m$ lines contain two integers $u$ and $v$ ($1 \leq u$, $v \leq n$) denoting an undirected edge between the two nodes.

The next line contains four integers $s$, $b$, $k$ and $h$ ($1 \leq s$, $b \leq 1000$, $0 \leq k$, $h \leq 10^9$), the number of spaceships, the number of bases, the cost of having a base attacked, and the cost of creating a dummy base, respectively.

The next $s$ lines contain three integers $x$, $a$, $f$ ($1 \leq x \leq n$, $0 \leq a$, $f \leq 10^9$), denoting the location, attack, and fuel of the spaceship.

The next $b$ lines contain two integers $x$, $d$ ($1 \leq x \leq n$, $0 \leq d \leq 10^9$), denoting the location and defence of the base.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 100$，$0 \leq m \leq 10000$），分别表示节点数和边数。

接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示节点 $u$ 与节点 $v$ 之间存在一条无向边。

下一行包含四个整数 $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$），分别表示该基地的位置和防御力。

Print a single integer, the minimum cost in terms of gold.

输出一个整数，即以金币为单位的最小花费。

One way to minimize the cost is to build $4$ dummy bases, for a total cost of $4 \times 3 = 12$.

One empire spaceship will be assigned to attack each of these dummy bases, resulting in zero actual bases attacked.

最小化成本的一种方法是建造 $4$ 个虚拟基地，总成本为 $4 \times 3 = 12$。

每个虚拟基地将分配一艘帝国飞船进行攻击，因此实际被攻击的基地数量为零。