题目描述

小明是养成类游戏高手。

一天他看到一个视频，介绍一款卡牌游戏，玩家要在一个地图上不断前进，途径各个功能的商店，并最终走到终点迎接最终的挑战。途中，玩家可能会获得一张新卡，或者可以选择增强一张已有的卡，又或者直接提高自己最后的战力。在最后的挑战中，玩家卡组里最强大的一张卡将自动成为主力，在战斗中直接发挥主导作用。

小明作为养成类游戏资深强度党，他深知如果提前获知游戏的所有机制以及整个地图的结构，他将能够轻松得知最终战斗时自己能够达到的最强战力。经过他的搜索，这个游戏的卡组机制大致如下：游戏地图可以看作一个 $n$ 个点 $m$ 条边的有向无环图，玩家从节点 $1$ 出发，经过若干个节点后到达节点 $n$ 迎接挑战，期间每个节点都可能有特殊事件发生，具体有以下五种：

0. 无特殊事件；
1. 获得一张能力值为 $(a_i,b_i)$ 的卡牌；
2. 选择已有的一张卡牌，并将其 $a$ 加上 $x_i$；
3. 选择已有的一张卡牌，并将其 $b$ 加上 $y_i$；
4. 最终之战的战力永久提高 $w_i$。

并且节点 $1$ 和节点 $n$ 一定没有特殊事件发生。在最终挑战时，玩家可以选择一张自己持有的卡牌，并将其 $a$ 变为原来的 $10^9$ 倍。最终之战的战力为路径上永久提升的综合加上所有卡牌的 $a$ 与 $b$ 乘积的和。小明一眼就看出最后能达到的最大战力了，所以他也希望你能跟他一眼看出来。他说，你只需要告诉他最大战力是多少就行了，不需要告诉他方案。

输入格式

第一行两个正整数 $n,m$，表示地图的节点数与边数。

之后的 $n$ 行，每行若干个整数表示一个节点的类型与参数。具体地，其一定是以下五种格式中的一种：

• $0$；
• $1\ a_i\ b_i$；
• $2\ x_i$；
• $3\ y_i$；
• $4\ w_i$。

之后的 $m$ 行，每行一个两个正整数 $u,v$，描述一条 $u\to v$ 的有向边。

由于小明想要方便你作答，小明专门把无法到达终点的部分或起点无法到达的部分去除掉了，并且帮你整理了点的编号，使得有 $u<v$。

输出格式

输出一个整数，表示所有策略下最终战力的最大值。

输入输出样例

样例输入1

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

样例输出1

60000000015000

其余样例见下发文件，其分别满足下表中每一个子任务的性质。

数据范围

对于 $100\%$ 的数据，$2\le n\le200,n-1\le m\le\min(\frac{n(n-1)}2,2000),1\le a_i,b_i,x_i,y_i\le200,1\le w_i\le10^6$，保证输入没有重边，且对于每个节点 $i$，均存在一条 $1$ 至 $n$ 的路径且该路径经过 $i$。

本题采用子任务测试，且会有极大的合理子任务依赖。只有你通过了一个子任务中的所有测试点，且通过了其所有依赖子任务时，才可得到该子任务的分数。