310713: CF1874G. Jellyfish and Inscryption

G. Jellyfish and Inscryptiontime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

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 < 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.

Input

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 < 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$.

Output

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

ExamplesInput

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

Output

100000000000

Input

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

Output

2000000

Input

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

Output

20000000005600

Input

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

Output

80000000001000

Input

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

Output

60000000015000

Input

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

Output

133000000040

Note

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

题目大意：
Jellyfish喜欢玩一个名为"Inscryption"的游戏，游戏在一个有n个顶点和m条边的有向无环图上进行。所有边a→b满足a < b。你需要从顶点1移动到顶点n，然后与最终boss战斗。在过程中，你会收集卡片和道具。每张卡片有两个属性：HP和伤害。如果一个卡片的HP是a，伤害是b，那么这张卡片的力量是a×b。每个道具只有一个属性：力量。除了顶点1和顶点n，还有一些顶点会触发特殊事件。特殊事件包括：1. 你将获得一张HP为a，伤害为b的卡片。2. 如果你至少有一张卡片，选择一张卡片并将其HP增加x。3. 如果你至少有一张卡片，选择一张卡片并将其伤害增加y。4. 你将获得一个力量为w的道具。当你到达顶点n时，你可以选择最多一张卡片，并将其伤害乘以10^9。最终boss非常强大，所以你想要最大化所有卡片和道具的力量之和。如果你以最佳方式玩游戏，找到所有卡片和道具力量之和的最大可能值。

输入输出数据格式：
输入：
第一行包含两个整数n和m（2≤n≤200，n-1≤m≤min(n(n-1)/2, 2000)）——顶点数和边数。
接下来n行，第i行（1≤i≤n）描述在顶点i将触发的特殊事件：
0 —— 无特殊事件。
1 a b（1≤a, b≤200）—— 你将获得一张HP为a，伤害为b的卡片。
2 x（1≤x≤200）—— 如果你至少有一张卡片，选择一张卡片并将其HP增加x。
3 y（1≤y≤200）—— 如果你至少有一张卡片，选择一张卡片并将其伤害增加y。
4 w（1≤w≤10^6）—— 你将获得一个力量为w的道具。
接下来m行，每行包含两个整数u和v（1≤u 保证每条边(u,v)最多出现一次。
保证顶点1和顶点n上没有特殊事件。
保证对于所有i，存在一条从顶点1到顶点n且经过顶点i的路径。
输出：
输出一个整数——所有卡片和道具力量之和的最大可能值。题目大意： Jellyfish喜欢玩一个名为"Inscryption"的游戏，游戏在一个有n个顶点和m条边的有向无环图上进行。所有边a→b满足a < b。你需要从顶点1移动到顶点n，然后与最终boss战斗。在过程中，你会收集卡片和道具。每张卡片有两个属性：HP和伤害。如果一个卡片的HP是a，伤害是b，那么这张卡片的力量是a×b。每个道具只有一个属性：力量。除了顶点1和顶点n，还有一些顶点会触发特殊事件。特殊事件包括：1. 你将获得一张HP为a，伤害为b的卡片。2. 如果你至少有一张卡片，选择一张卡片并将其HP增加x。3. 如果你至少有一张卡片，选择一张卡片并将其伤害增加y。4. 你将获得一个力量为w的道具。当你到达顶点n时，你可以选择最多一张卡片，并将其伤害乘以10^9。最终boss非常强大，所以你想要最大化所有卡片和道具的力量之和。如果你以最佳方式玩游戏，找到所有卡片和道具力量之和的最大可能值。 输入输出数据格式： 输入： 第一行包含两个整数n和m（2≤n≤200，n-1≤m≤min(n(n-1)/2, 2000)）——顶点数和边数。 接下来n行，第i行（1≤i≤n）描述在顶点i将触发的特殊事件： 0 —— 无特殊事件。 1 a b（1≤a, b≤200）—— 你将获得一张HP为a，伤害为b的卡片。 2 x（1≤x≤200）—— 如果你至少有一张卡片，选择一张卡片并将其HP增加x。 3 y（1≤y≤200）—— 如果你至少有一张卡片，选择一张卡片并将其伤害增加y。 4 w（1≤w≤10^6）—— 你将获得一个力量为w的道具。 接下来m行，每行包含两个整数u和v（1≤u