← 返回题目列表

Codeforces · 1184/B2

B2. 医生遇见维德(中)

中文机器翻译题面 查看原题

在博士的帮助下,叛军成功窃取了足够的黄金,对帝国发起全面进攻!然而,达斯·维达正在寻求复仇并想要夺回他的黄金。

叛军将黄金隐藏在整个银河系的各个基地中。达斯·维德和帝国正在寻求派出他们的宇宙飞船来攻击这些基地。

星系可以表示为一个无向图,其中包含 $$$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$$$。

将指派一艘帝国飞船攻击这些虚拟基地,导致实际基地被攻击为零。