杀戮尖塔第四厉害高手
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

故障机器人正在玩一款名为《Slay the Spire》的游戏，他的目标是成为杀戮尖塔第四厉害的高手。
游戏地图由 n 个节点组成，故障机器人从节点 1 出发，目标是到达节点 n 。
该游戏满足以下性质：
1. 地图由 m 条有向边组成，故障机器人可以通过有向边从一个节点移动到另一个节点。
2. 定义 d_i 为从节点 1 到节点 i 的简单路径的距离（保证从节点 1 到节点 i 的所有简单路径距离相同，并且对于 \forall {i < n} 都有 d_n > d_i）。
3. 所有有向边 (u_i, v_i) 满足 d_{v_i}=d_{u_i}+1。
4. 故障机器人有一个战斗力属性 k 。
5. 每个节点 i 有两个属性战力要求和收益，用 a_i 和 b_i 表示：
  • 当 k < a_i 时，玩家进入节点 i 后会被打败然后游戏结束。
  • 当 k \geq a_i 时，玩家进入节点 i 后 k=k+b_i 。
6. 故障机器人拥有一个遗物羽翼之靴，可使他从当前节点 i 传送到任意满足 d_j=d_i+1 的节点 j , 最多传送 3 次。

故障机器人想知道他是否能够从节点 1 到达节点 n。
补充说明：
  • 保证节点 1 到任何一个节点都存在一条路径。
  • 保证任何节点都存在一条路径能够到达节点 n。
  • 保证图中不存在自环和重边。

输入描述:

第一行，输入三个整数 n, m 和 k（2 \leq n \leq 2 \cdot 10^5，n - 1 \leq m \leq 2 \cdot 10^5，1 \leq k \leq 10^9），分别表示节点数，边数和角色初始战斗力。
接下来 n 行，每行输入两个整数 a_i 和 b_i （1 \leq a_i \leq 10^9, \space -10^9 \leq b_i \leq 10^9），表示节点 i 的战斗力要求和收益。
接下来 m 行，每行输入两个整数 u_i 和 v_i（1 \leq u_i,v_i \leq n, \space u_i \neq v_i），表示一条从 u_i 到 v_i 的有向边。

输出描述:

一行，如果故障机器人能够到达节点 n，输出 "YES"（不含引号），否则输出 "NO"（不含引号）。
示例1

输入

复制 
7 9 10
1 5
15 10
20 1
21 20
30 15
1 2
27 -100
1 2
1 3
1 4
2 5
3 5
4 6
3 6
5 7
6 7

输出

复制 
YES

说明


样例如图所示：
故障机器人可以通过以下操作来到达节点 n 。
1. 进入节点 1 ，此时攻击力为 15 。
2. 从节点 1 到达节点 2，此时攻击力为 25。
3. 使用羽翼之靴从节点 2 到达节点 6，此时攻击力为 27 。
4. 从节点 6 到达节点 7 ，游戏结束。
示例2

输入

复制 
5 5 888
755 -859
15 16
20 805
54 -348
1000 -896
1 2
1 3
2 4
3 4
4 5

输出

复制 
NO

说明

此样例中，故障机器人无论如何操作都无法到达节点 n 。