CF1874G.Jellyfish and Inscryption

Jellyfish loves playing a game called "Inscryption" which is played on a directed acyclic graph with $n$ vertices and $m$ edges. All edges $a \to b$ satisfy $a \lt b$.

You need to move from vertex $1$ to vertex $n$ along the directed edges, and then fight with the final boss.

You will collect cards and props in the process.

Each card has two attributes: HP and damage. If a card's HP is $a$ and its damage is $b$, then the power of the card is $a \times b$.

Each prop has only one attribute: power.

In addition to vertex $1$ and vertex $n$, there are some vertices that trigger special events. The special events are:

1. You will get a card with $a$ HP, and $b$ damage.
2. If you have at least one card, choose one of your cards and increase its HP by $x$.
3. If you have at least one card, choose one of your cards and increase its damage by $y$.
4. You will get a prop with $w$ power.

When you get to vertex $n$, you can choose at most one of your cards and multiply its damage by $10^9$.

The final boss is very strong, so you want to maximize the sum of the power of all your cards and props. Find the maximum possible sum of power of all your cards and props if you play the game optimally.

水母很喜欢玩一款名为“Inscryption”的游戏，该游戏在一个包含 $n$ 个顶点和 $m$ 条边的有向无环图上进行。所有边 $a \to b$ 均满足 $a \lt b$。

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

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

每张卡牌有两个属性：生命值（HP）和攻击力（damage）。若某张卡牌的 HP 为 $a$、攻击力为 $b$，则该卡牌的强度（power）为 $a \times b$。

每个道具只有一个属性：强度（power）。

除顶点 $1$ 和顶点 $n$ 外，图中还存在若干触发特殊事件的顶点。这些特殊事件包括：

1. 获得一张 HP 为 $a$、攻击力为 $b$ 的卡牌；
2. 若你至少拥有一张卡牌，则可选择其中一张，将其 HP 增加 $x$；
3. 若你至少拥有一张卡牌，则可选择其中一张，将其攻击力增加 $y$；
4. 获得一个强度为 $w$ 的道具。

当你抵达顶点 $n$ 时，你可以至多选择一张你所拥有的卡牌，并将其攻击力乘以 $10^9$。

最终 Boss 非常强大，因此你希望最大化你所拥有全部卡牌与道具的强度总和。若你以最优策略进行游戏，求此强度总和的最大可能值。

The first line contains two integers $n$ and $m$ ($2 \leq n \leq 200$, $n - 1\leq m \leq \min(\frac{n(n-1)}2, 2000)$) — the number of the vertices and the number of the edges.

In the following $n$ lines, the $i$-th $(1 \leq i \leq n)$ line describes the special event that will trigger on vertex $i$:

• 0 — no special events.
• 1 a b ($1 \leq a, b \leq 200$) — you will get a card with $a$ HP, and $b$ damage.
• 2 x ($1 \leq x \leq 200$) — if you have at least one card, choose one of your cards and increase its HP by $x$.
• 3 y ($1 \leq y \leq 200$) — if you have at least one card, choose one of your cards and increase its damage by $y$.
• 4 w ($1 \leq w \leq 10^6$) — you will get a prop with $w$ power.

In the following $m$ lines, each line contains two integers $u$ and $v$ ($1 \leq u \lt v \leq n$) representing a directed edge from vertex $u$ to vertex $v$.

It is guaranteed that every edge $(u,v)$ appears at most once.

It is guaranteed that there are no special events on vertex $1$ and vertex $n$.

It is guaranteed that for all $i$, there exists a path from vertex $1$ to vertex $n$ that passes through vertex $i$.

第一行包含两个整数 $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$ 点生命值（HP）和 $b$ 点攻击力（damage）的卡牌。
• 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$ 点力量（power）的道具。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \leq u \lt v \leq n$），表示一条从顶点 $u$ 指向顶点 $v$ 的有向边。

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

保证顶点 $1$ 和顶点 $n$ 上均无特殊事件。

保证对任意 $i$，均存在一条从顶点 $1$ 到顶点 $n$ 的路径，且该路径经过顶点 $i$。

Output a single integer — the maximum sum of the power of all your cards and props.

输出一个整数——你所有卡片和道具的力量值之和的最大值。

In the first example, we will play the game in the following order:

• move from vertex $1$ to vertex $2$, get a card with $2$ HP, and $10$ damage.
• move from vertex $2$ to vertex $4$, choose the card we get from vertex $2$ and increase its HP by $8$.
• move from vertex $4$ to vertex $6$, choose the card we get from vertex $2$ and multiply its damage by $10^9$.

In the end, we will have a card with $(2+8)=10$ HP and $10 \times 10^9=10^{10}$ damage, It's power is $10 \times 10^{10}=10^{11}$. Because we only have the card we get from vertex $2$, so the sum of power of all your cards and props is $10^{11}$.

在第一个例子中，我们将按以下顺序进行游戏：

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

最终，我们将拥有一张生命值为 $(2+8)=10$、伤害为 $10 \times 10^9=10^{10}$ 的卡牌，其力量值为 $10 \times 10^{10}=10^{11}$。由于我们仅拥有在顶点 $2$ 获得的这张卡牌，因此所有卡牌与道具的力量值总和为 $10^{11}$。