叛军已经积攒了足够的黄金来发动全面进攻。现在情况翻转了,叛军将派出飞船攻击帝国基地!
星系可以表示为一个无向图,其中包含 $$$n$$$ 行星(节点)和 $$$m$$$ 虫洞(边),每个虫洞连接两个行星。
总共$$$s$$$叛军飞船和$$$b$$$帝国基地位于银河系的不同星球。
每艘飞船都有一个位置$$$x$$$,表示其所在星球的索引,攻击强度$$$a$$$,一定量的燃料$$$f$$$,以及运行价格$$$p$$$。
每个基地都有一个位置 $$$x$$$、防御强度 $$$d$$$ 和一定数量的黄金 $$$g$$$。
如果满足以下两个条件,宇宙飞船就可以攻击基地:
- 飞船的攻击强度大于或等于基地的防御强度
- 宇宙飞船的燃料大于或等于宇宙飞船节点和基地节点之间的最短距离(以虫洞数量计算)
叛军是非常自豪的战士。因此,如果一艘宇宙飞船无法攻击任何基地,叛军飞行员就不会接受操作它。
如果操作一艘飞船,该飞船所产生的利润等于其攻击的基地的黄金减去操作该飞船的费用。请注意,这可能是负数。一艘被操纵的飞船将会攻击使其利润最大化的基地。
达斯·维德总是喜欢显得富有。因此,每当一个基地被攻击并且其黄金被盗时,他都会确保立即为该基地补充黄金。
因此,对于叛军来说,多艘飞船可以攻击同一个基地,这样每艘飞船仍然会获得该基地的所有黄金。
叛军要求海蒂和博士决定操作哪组宇宙飞船,以实现总利润最大化。
然而,由于战争持续了很长时间,飞行员们之间已经形成了牢不可破的羁绊,如果他们的朋友不也在操作飞船,他们中的一些人就会拒绝操作飞船。
它们有一个 $$$k$$$ 依赖关系列表,其形式为 $$$s_1, s_2$$$,表示只有当太空飞船 $$$s_2$$$ 也被操作时,太空飞船 $$$s_1$$$ 才能被操作。
输入
输入的第一行包含整数 $$$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$$$ 的依赖性。
输出
打印单个整数,可以实现的最大总利润。
示例
输入 #1
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
输出 #1
2
注意
最优策略是操作飞船 1、2 和 4,分别攻击基地 1、1 和 2。