102893: [Atcoder]ABC289 D - Step Up Robot

Problem Statement

There is a staircase with infinite steps. The foot of the stairs is the $0$-th step, the next step is the $1$-st step, the next is the $2$-nd, and so on.

There is a stair-climbing robot on the $0$-th step. The robot can climb up $A _ 1,A _ 2,\ldots$, or $A _ N$ steps at a time. In other words, when the robot is on the $i$-th step, it can step onto one of the $(i+A _ 1)$-th step, $(i+A _ 2)$-th step, $\ldots$, and $(i+A _ N)$-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.

There are traps on the $B _ 1$-th, $B _ 2$-th, $\ldots$, and $B _ M$-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.

The robot wants to step onto the $X$-th step. Determine whether it is possible to do so.

Constraints

• $1\leq N\leq10$
• $1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5$
• $1\leq M\leq10^5$
• $1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
$M$
$B _ 1$ $B _ 2$ $\ldots$ $B _ M$
$X$

Output

In a single line, print Yes if the robot can step onto the $X$-th step, and No otherwise.

Sample Input 1

3
3 4 5
4
4 5 6 8
15

Sample Output 1

Yes

For example, the robot can reach the $15$-th step as follows.

• Climb up $3$ steps. The robot is now on the $3$-rd step.
• Climb up $4$ steps. The robot is now on the $7$-th step.
• Climb up $5$ steps. The robot is now on the $12$-th step.
• Climb up $3$ steps. The robot is now on the $15$-th step.

Sample Input 2

4
2 3 4 5
4
3 4 5 6
8

Sample Output 2

No

No matter how the robot moves, it cannot step onto the $8$-th step.

Sample Input 3

4
2 5 7 8
5
2 9 10 11 19
20

Sample Output 3

Yes

问题描述

有一个无限级的楼梯。楼梯的底部是第0级台阶，下一个台阶是第1级台阶，再下一个台阶是第2级台阶，以此类推。

有一个楼梯攀爬机器人在第0级台阶上。机器人可以一次爬升A₁、A₂、……或A_N级台阶。也就是说，当机器人在第i级台阶时，它可以一步跳到第(i+A₁)级台阶、第(i+A₂)级台阶、……和第(i+A_N)级台阶，但不能一步跳到其他台阶。机器人也不能向下走台阶。

在第B₁级、B₂级、……和B_M级台阶上都有陷阱。一旦机器人踏上一个有陷阱的台阶，它就无法再移动了。

机器人想要踏上第X级台阶。确定是否可以做到这一点。

约束

• 1≤N≤10
• 1≤A₁＜A₂＜……＜A_N≤10⁵
• 1≤M≤10⁵
• 1≤B₁＜B₂＜……＜B_M＜X≤10⁵
• 输入中的所有值都是整数。

输入

输入从标准输入中给出，格式如下：

$N$
$A _ 1$ $A _ 2$ $\ldots$ $A _ N$
$M$
$B _ 1$ $B _ 2$ $\ldots$ $B _ M$
$X$

输出

在一行中，如果机器人可以踏上第X级台阶，则打印Yes，否则打印No。

样例输入1

3
3 4 5
4
4 5 6 8
15

样例输出1

Yes

例如，机器人可以按以下方式到达第15级台阶：

• 爬升3级台阶。机器人现在在第3级台阶上。
• 爬升4级台阶。机器人现在在第7级台阶上。
• 爬升5级台阶。机器人现在在第12级台阶上。
• 爬升3级台阶。机器人现在在第15级台阶上。

样例输入2

4
2 3 4 5
4
3 4 5 6
8

样例输出2

No

无论机器人如何移动，它都无法踏上第8级台阶。

样例输入3

4
2 5 7 8
5
2 9 10 11 19
20

样例输出3

Yes