CF1874G Jellyfish and Inscryption

水母喜欢玩一个叫做“Inscryption”的游戏，这个游戏在一个有向无环图上进行，图中有 $n$ 个顶点和 $m$ 条边。所有的边 $a \to b$ 都满足 $a < b$。 你需要沿着有向边从顶点 $1$ 移动到顶点 $n$，然后与最终 Boss 战斗。 在这个过程中，你会收集卡牌和道具。 每张卡牌有两个属性：生命值（HP）和伤害（damage）。如果一张卡牌的生命值为 $a$，伤害为 $b$，那么这张卡牌的能量为 $a \times b$。 每个道具只有一个属性：能量值（power）。 除了顶点 $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$ 行（$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$ 移动到顶点 $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}$。 由 ChatGPT 4.1 翻译