CF1184B2 The Doctor Meets Vader (Medium)

多亏了博士的帮助，叛军才偷到了足够的黄金，对帝国发动了全面进攻！然而，达斯-维德正在复仇，想要夺回他的黄金。 叛军把黄金藏在了银河系的各个基地。达斯-维达和帝国希望派出飞船攻击这些基地。 银河系可以表示为一个无向图，其中有 $ 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 $ ) ，表示基地的位置和防御。

打印一个整数，以黄金为单位的最低成本。 #### 样例 #1 #### 样例输入 #1 ``` 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 ``` #### 样例输出 #1 ``` 12 ```

使成本最小化的一种方法是建造 $4$ 个 $3$ 美元的虚拟基地，总成本为 $4\times 3 = 12$ 美元。 一艘帝国飞船将被分配去攻击每个假基地，结果是实际被攻击的基地为零。