Score : $400$ points

问题描述

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

有一个爬楼梯机器人位于第0级台阶上。该机器人每次可以向上爬$A_1,A_2,\ldots$或$A_N$级台阶。换句话说，当机器人处于第i级台阶时，它可以一步跨到$(i+A_1)$级、$(i+A_2)$级、……或$(i+A_N)$级台阶中的任意一级，但不能跨到其他级台阶。同时，机器人也不能向下走楼梯。

在第$B_1$级、第$B_2$级、……和第$B_M$级台阶上设有陷阱。一旦机器人踏上带有陷阱的台阶，它将无法再移动。

机器人想要到达第X级台阶。请判断是否有可能实现这一目标。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 12:04:37