J2 例题-8 跳跃游戏

题目描述

喵喵站在数轴的坐标 $0$ 处，她只能向数轴的正方向跳跃。 她准备尝试 $N$ 次跳跃。在第 $i$ 次跳跃中，它可以从第 $x$ 格跳到 $x+a_i$ 或 $x+b_i$ 格。 请问：在 $N$ 次跳跃之后，他是否可能在坐标 $X$ 处？

输入格式

第一行两个整数，分别为 $N$ 和 $X$，表示跳跃的次数和终点的坐标。 接下来 $n$ 行，每行两个整数，分别表示第 $i$ 跳可以正向移动的距离 $a_i$ 和 $b_i$。

输出格式

如果喵喵在 $N$ 次跳跃后可能位于坐标 $X$，则输出 Yes；否则，输出 No。

样例输入

2 10
3 6
4 5

样例输出1

Yes

样例解析

通过在第一跳移动 $b_1(=6)$，在第二跳移动 $a_2(=4)$ 时，他可以位于坐标 $X(=10)$。

数据范围

对于 $100\%$ 的数据：$1 \le N \le 100$，$1 \leq a_i \lt b_i \leq 100 \,$，$1 \leq X \leq 10000$。