AT_abc289_d [ABC289D] Step Up Robot

题目描述

有一座无限延伸的楼梯。最底下是第 $0$ 层，每上升 $1$ 层，依次为第 $1$ 层、第 $2$ 层，依此类推。

现在有一个“楼梯登顶机器人”位于第 $0$ 层。这个机器人每次可以选择上升 $A_1, A_2, \ldots, A_N$ 层中的任意一个步长。也就是说，如果机器人当前在第 $i$ 层，则一次操作后可以到达第 $i+A_1$ 层、第 $i+A_2$ 层、⋯、第 $i+A_N$ 层中的任意一层。机器人不能一次操作上升其它步数，也不能下楼。

在第 $B_1, B_2, \ldots, B_M$ 层上放置了麻糬（“モチ”）。如果机器人到达有麻糬的楼层，则会被困住，无法再移动到其它楼层。

请判断机器人是否可以恰好到达第 $X$ 层。

输入格式

输入按以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$ $M$ $B_1$ $B_2$ $\ldots$ $B_M$ $X$

输出格式

如果机器人可以恰好到达第 $X$ 层，输出 Yes；否则输出 No。

输入输出样例 #1

输入 #1

3
3 4 5
4
4 5 6 8
15

输出 #1

Yes

输入输出样例 #2

输入 #2

4
2 3 4 5
4
3 4 5 6
8

输出 #2

No

输入输出样例 #3

输入 #3

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

输出 #3

Yes

说明/提示

限制条件

• $1 \leq N \leq 10$
• $1 \leq A_1 < A_2 < \cdots < A_N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq B_1 < B_2 < \cdots < B_M < X \leq 10^5$
• 所有输入均为整数

样例解释 1

例如，可以按如下方式到达第 $15$ 层：

• 上升 $3$ 层，机器人到达第 $3$ 层。
• 上升 $4$ 层，机器人到达第 $7$ 层。
• 上升 $5$ 层，机器人到达第 $12$ 层。
• 上升 $3$ 层，机器人到达第 $15$ 层。

样例解释 2

无论如何移动，机器人都无法恰好到达第 $8$ 层。

由 ChatGPT 4.1 翻译