#P18671. Stage Clear

    ID: 18007 传统题 7000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-子集 DP暴力枚举阈值划分大小情况相邻交换确定比较规则堆贪心交换论证普通并查集懒删除

Stage Clear

Stage Clear

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

战场包含 nn 个交叉点,编号为 1,2,…,n1,2,\ldots,n,以及连接这些点的 mm 条有向通路。因此,战场可以看作一张有向无环图。玩家最初位于交叉点 11,拥有 XX 点生命值,简称 HP。

除交叉点 11 外,每个交叉点都有一只怪物。玩家第一次进入某个交叉点时,必须与该点的怪物战斗。战斗中,玩家会先失去 aia_i 点 HP;击败怪物后,得到 bib_i 点 HP 作为奖励。

当 HP 变成负数(小于 00)时,游戏立即结束,因此不能让这种情况发生。HP 恰好为 00 时不会结束游戏,也就是说,扣除 aia_i 后恰好为 00 仍然可以获得随后的奖励。

如果玩家多次经过同一个交叉点,只有第一次需要战斗,已经击败的怪物不会复活。玩家可以沿给定有向通路移动,也可以使用魔法飞回交叉点 11。可以多次飞回,飞回本身不消耗 HP。保证玩家能够从交叉点 11 到达每个交叉点。

击败全部怪物后,Prof.Chen 就能通过这一关。请计算完成这一目标所需的最小初始 HP。

输入格式

第一行包含两个整数 n,mn,m,满足 n≥2n\ge2、m≥n−1m\ge n-1、n+m≤72n+m\le72,分别表示交叉点数和有向通路数。

接下来的 n−1n-1 行,依次描述交叉点 2,3,…,n2,3,\ldots,n 的怪物。每行包含两个整数 ai,bia_i,b_i,满足 1≤ai,bi≤10151\le a_i,b_i\le10^{15}。

接下来的 mm 行,每行包含两个整数 ui,viu_i,v_i,满足 1≤ui<vi≤n1\le u_i<v_i\le n,表示一条从 uiu_i 到 viv_i 的有向通路。任意一对交叉点之间至多有一条给定通路。

保证从交叉点 11 能够到达每个交叉点。本题只有一组数据,开头没有测试组数。

输出格式

输出一行一个整数,表示击败全部怪物所需的最小初始 HP。

样例输入 1

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

样例输出 1

4