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}$$$。