题目描述

z 去山里灵活家提亲。稻妻的地图是 $N$ 个点 $M$ 条边组成的有向无环图，山里灵活的家在 $N$ 号点，z 要从 $1$ 号点到 $N$ 号点。

山里灵活为了考察 z，设定了浮动彩礼。z 每经过一条边，需要缴纳一定的彩礼。边分为两类：

• 固定价格。经过该条有向边，z 需要交的彩礼钱是固定的。
• 固定比例。经过该条有向边，z 身上剩余的钱将乘以一个固定的数量，向下取整，其他钱全都要交彩礼。

每次交彩礼，至少交一单位的钱。如果交不上彩礼，就不能通过这条边。请问 z 出门时，至少带多少单位的钱？

输入格式

输入共 $M+1$ 行。

输入的第一行为两个整数 $N,M$。

接下来 $M$ 行，每行四个数：

• 1 p u v，表示这条边固定缴纳 $p$ 单位钱彩礼，由 $u$ 指向 $v$。$p$ 为整数。
• 2 w u v，表示这条边交纳固定比例彩礼，假设进入这条边前剩余 $k$ 单位钱，离开这条边时剩余 $\lfloor wk\rfloor$ 单位钱，交纳 $k-\lfloor wk\rfloor$ 单位钱。边由 $u$ 指向 $v$。$w$ 是一个 $(0,1)$ 间的浮点数，小数点后最多三位。

输出格式

输出一行一个整数，代表最少携带的钱的数目。

4 4
1 3 1 2
2 0.2 1 3
1 2 2 4
2 0.2 3 4

5

数据规模与约定

• 对于 $10\%$ 的测试数据，为一条链。
• 对于另外 $20\%$ 的测试数据，$m \le 1000$。
• 对于 $100\%$ 的测试数据，$n \le 1000$，$m \le 10^6$，所需钱总数不超过 $10^9$。