/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
無限に続く階段があります。 一番下は 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 段目にのぼりたいです。 階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。
制約
- 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
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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
例えば、次のようにして 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
Score : 400 points
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