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 \le n \le 200, n-1 \le m \le \min(\frac{n(n-1)}{2}, 2000)$) —— 顶点的数量和边的数量。

接下来的 $n$ 行中，第 $i$ 行 ($1 \le i \le n$) 描述了在顶点 $i$ 触发的特殊事件：

• $0$ —— 无特殊事件。
• $1 \ a \ b$ ($1 \le a, b \le 200$) —— 你将获得一张生命值为 $a$，伤害为 $b$ 的卡牌。
• $2 \ x$ ($1 \le x \le 200$) —— 如果你至少拥有一张卡牌，选择你的一张卡牌并将其生命值增加 $x$。
• $3 \ y$ ($1 \le y \le 200$) —— 如果你至少拥有一张卡牌，选择你的一张卡牌并将其伤害增加 $y$。
• $4 \ w$ ($1 \le w \le 10^6$) —— 你将获得一个战力为 $w$ 的道具。

接下来的 $m$ 行中，每行包含两个整数 $u$ 和 $v$ ($1 \le u < v \le 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

说明

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

• 从顶点 $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}$。

输入格式 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