#P18671. Stage Clear
Stage Clear
Stage Clear
Prof.Chen 非常喜欢玩电脑游戏。现在,他正在游戏中与可怕的怪物战斗。
战场包含 个交叉点,编号为 ,以及连接这些点的 条有向通路。因此,战场可以看作一张有向无环图。玩家最初位于交叉点 ,拥有 点生命值,简称 HP。
除交叉点 外,每个交叉点都有一只怪物。玩家第一次进入某个交叉点时,必须与该点的怪物战斗。战斗中,玩家会先失去 点 HP;击败怪物后,得到 点 HP 作为奖励。
当 HP 变成负数(小于 )时,游戏立即结束,因此不能让这种情况发生。HP 恰好为 时不会结束游戏,也就是说,扣除 后恰好为 仍然可以获得随后的奖励。
如果玩家多次经过同一个交叉点,只有第一次需要战斗,已经击败的怪物不会复活。玩家可以沿给定有向通路移动,也可以使用魔法飞回交叉点 。可以多次飞回,飞回本身不消耗 HP。保证玩家能够从交叉点 到达每个交叉点。
击败全部怪物后,Prof.Chen 就能通过这一关。请计算完成这一目标所需的最小初始 HP。
输入格式
第一行包含两个整数 ,满足 、、,分别表示交叉点数和有向通路数。
接下来的 行,依次描述交叉点 的怪物。每行包含两个整数 ,满足 。
接下来的 行,每行包含两个整数 ,满足 ,表示一条从 到 的有向通路。任意一对交叉点之间至多有一条给定通路。
保证从交叉点 能够到达每个交叉点。本题只有一组数据,开头没有测试组数。
输出格式
输出一行一个整数,表示击败全部怪物所需的最小初始 HP。
样例输入 1
4 4
4 2
5 3
2 6
1 2
1 3
2 4
3 4
样例输出 1
4