← 返回题目列表

Codeforces · 1874/G

G. 水母和密码

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

Jellyfish 喜欢玩一种名为“Inscryption”的游戏,该游戏在具有 $$$n$$$ 个顶点和 $$$m$$$ 边的有向无环图上进行。所有边 $$$a \to b$$$ 满足 $$$a < b$$$。

你需要沿着有向边从顶点$$$1$$$移动到顶点$$$n$$$,然后与最终boss战斗。

您将在此过程中收集卡牌和道具。

每张卡有两个属性:生命值和伤害。如果一张卡牌的 HP 为 $$$a$$$,其伤害为 $$$b$$$,则该卡牌的威力为 $$$a \times b$$$。

每个道具只有一个属性:力量。

除了顶点$$$1$$$和顶点$$$n$$$之外,还有一些顶点会触发特殊事件。特别活动有:

1. 你将获得一张具有$$$a$$$生命值和$$$b$$$伤害的卡牌。
2. 如果你至少有一张卡牌,选择你的一张卡牌并增加其生命值$$$x$$$。
3. 如果你至少有一张牌,选择你的一张牌并使其伤害增加$$$y$$$。
4.你将获得一个具有$$$w$$$力量的道具。

当你到达顶点$$$n$$$时,你最多可以选择一张牌,并将其伤害乘以$$$10^9$$$。

最终的boss非常强大,所以你想要最大化你所有卡牌和道具的力量总和。如果您以最佳方式玩游戏,请找到所有卡牌和道具的最大可能力量总和。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \leq n \leq 200$$$, $$$n - 1\leq m \leq \min(\frac{n(n-1)}2, 2000)$$$) — 顶点数和边数。

在下面的 $$$n$$$ 行中,第 $$$i$$$-th $$$(1 \leq i \leq n)$$$ 行描述了将在顶点 $$$i$$$ 上触发的特殊事件:

- 0 — 无特殊事件。
- 1 a b ($$$1 \leq a, b \leq 200$$$) — 您将获得一张具有 $$$a$$$ 生命值和 $$$b$$$ 伤害的卡牌。
- 2 x ($$$1 \leq x \leq 200$$$) - 如果您至少有一张牌,请选择一张牌并将其生命值增加 $$$x$$$。
- 3 y ($$$1 \leq y \leq 200$$$) - 如果您至少有一张牌,请选择一张牌并将其伤害提高 $$$y$$$。
- 4 w ($$$1 \leq w \leq 10^6$$$) — 您将获得具有 $$$w$$$ 力量的道具。

在下面的 $$$m$$$ 行中,每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u < v \leq n$$$) 表示从顶点 $$$u$$$ 到顶点 $$$v$$$ 的有向边。

保证每条边 $$$(u,v)$$$ 最多出现一次。

保证顶点$$$1$$$和顶点$$$n$$$上没有特殊事件。

保证对于所有$$$i$$$,存在一条从顶点$$$1$$$到顶点$$$n$$$且经过顶点$$$i$$$的路径。

输出

输出一个整数——所有卡牌和道具的力量的最大总和。

示例

输入 #1

6 8
0
1 2 10
1 6 6
2 8
3 10
0
1 2
1 3
2 4
2 5
3 4
3 5
4 6
5 6

输出 #1

100000000000

输入 #2

4 3
0
4 1000000
4 1000000
0
1 2
2 3
3 4

输出 #2

2000000

输入 #3

16 15
0
1 1 10
1 10 1
2 4
3 4
1 20 20
2 30
3 20
1 1 100
2 9
1 1 200
2 9
3 10
1 190 100
2 10
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16

输出 #3

20000000005600

输入#4

9 9
0
1 1 200
3 200
3 200
3 200
3 200
1 200 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1 9

输出#4

80000000001000

输入 #5

9 8
0
1 20 200
3 200
3 200
2 5
1 100 200
3 200
3 200
0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9

输出 #5

60000000015000

输入 #6

16 34
0
0
0
2 6
3 1
4 27
4 40
3 9
0
2 6
1 8 1
0
2 2
1 10 7
2 9
0
2 4
3 10
2 11
2 7
13 15
3 15
2 3
6 14
4 12
10 12
9 10
7 8
4 13
11 12
4 6
11 16
14 15
2 5
5 15
9 13
8 14
1 3
2 15
12 16
7 10
4 5
1 2
4 11
4 9
4 16
3 6
6 8
7 11
15 16

输出 #6

133000000040

注意

在第一个示例中,我们将按以下顺序玩游戏:

- 从顶点 $$$1$$$ 移动到顶点 $$$2$$$,获得一张具有 $$$2$$$ 生命值和 $$$10$$$ 伤害的卡牌。
- 从顶点$$$2$$$移动到顶点$$$4$$$,选择我们从顶点$$$2$$$获得的卡牌,并将其生命值增加$$$8$$$。
- 从顶点$$$4$$$移动到顶点$$$6$$$,选择我们从顶点$$$2$$$获得的卡牌并将其伤害乘以$$$10^9$$$。

最终,我们将得到一张具有$$$(2+8)=10$$$生命值和$$$10 \times 10^9=10^{10}$$$伤害的卡牌,它的力量为$$$10 \times 10^{10}=10^{11}$$$。因为我们只有从顶点$$$2$$$获得的卡牌,所以你所有卡牌和道具的力量总和是$$$10^{11}$$$。