在博士的帮助下,叛军成功窃取了足够的黄金,对帝国发起全面进攻!然而,达斯·维达正在寻求复仇并想要夺回他的黄金。
叛军将黄金隐藏在整个银河系的各个基地中。达斯·维德和帝国正在寻求派出他们的宇宙飞船来攻击这些基地。
星系可以表示为一个无向图,其中包含 $$$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
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$$$ 虚拟底座,总成本为 $$$4 \times 3 = 12$$$。
将指派一艘帝国飞船攻击这些虚拟基地,导致实际基地被攻击为零。