Prof.Chen 非常喜欢玩电脑游戏。他现在正在游戏中与可怕的怪物战斗。

战场由 $n$ 个交叉路口组成，编号为 $1, 2, \dots, n$。这些交叉路口之间有 $m$ 条有向弧，使得战场可以被视为一个有向无环图。玩家现在位于交叉路口 $1$，拥有 $X$ 点生命值（HP）。

除了交叉路口 $1$ 之外，每个交叉路口都有一个怪物。当玩家第一次到达某个交叉路口时，他必须与该路口的怪物战斗。在战斗中，他会损失 $a_i$ 点 HP。当他最终击败怪物后，他将获得 $b_i$ 点 HP。注意，当 HP 变为负数（$< 0$）时，游戏结束，因此绝不能让这种情况发生。如果玩家多次访问同一个交叉路口，战斗只会在第一次访问时发生，因为怪物没有额外的生命。玩家只能沿着给定的 $m$ 条有向弧移动，或者通过魔法飞回交叉路口 $1$。玩家可以多次飞行，并且保证他总是能够到达每一个交叉路口。

当所有怪物都被清除后，Prof.Chen 即可通关。请编写一个程序来计算通关所需的最小初始 HP。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($n + m \le 72, n \ge 2, m \ge n - 1$)，分别表示交叉路口的数量和有向弧的数量。

接下来的 $n - 1$ 行，每行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 10^{15}$)，描述了交叉路口 $2, 3, \dots, n$ 处的怪物。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i < v_i \le n$)，表示一条从交叉路口 $u_i$ 到交叉路口 $v_i$ 的有向弧。任意两个交叉路口之间最多只有一条弧。

保证玩家可以从交叉路口 $1$ 到达每一个交叉路口。

输出格式

输出一行，包含一个整数，表示通关所需的最小初始 HP。

样例

样例输入 1

4 4
4 2
5 3
2 6
1 2
1 3
2 4
3 4

样例输出 1

4