题目描述

無限に続く階段があります。 一番下は $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$ 段目にのぼることが可能か判定してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

階段登りロボットが階段のちょうど $X$ 段目にのぼることができるとき Yes を、そうでないとき No を $1$ 行に出力せよ。

题目大意

有一机器人初始在 $0$ 级阶梯，对于每一级阶梯，机器人可以从 $1\sim N$ 种任选一个 $i$ 走 $A_i$ 步，同时有 $M$ 个障碍在 $B_i$ 级阶梯，若走到障碍则将无法移动，问能否通过某种方案使机器人到达第 $X$ 级阶梯。

$1\leq N\leq 10$，$1\leq M\leq 10^5$，$1\leq X\leq 10^5$，$A_i$ 和 $B_i$ 严格单调递增，$\forall i\in [1,M],B_i\neq X$。

3
3 4 5
4
4 5 6 8
15

Yes

4
2 3 4 5
4
3 4 5 6
8

No

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

Yes

提示

制約

• $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 $
• 入力はすべて整数

Sample Explanation 1

例えば、次のようにして $15$ 段目に到達することができます。 - 階段を $3$ 段のぼる。ロボットは $3$ 段目に移動する。 - 階段を $4$ 段のぼる。ロボットは $7$ 段目に移動する。 - 階段を $5$ 段のぼる。ロボットは $12$ 段目に移動する。 - 階段を $3$ 段のぼる。ロボットは $15$ 段目に移動する。

Sample Explanation 2

どのように移動しても階段登りロボットが階段のちょうど $8$ 段目にいることはできません。