配点 : $600$ 点

問題文

AtCoder 国には $A_1$ 円玉、$A_2$ 円玉、$A_3$ 円玉、$\dots$ 、$A_N$ 円玉の $N$ 種類のコインがあります。 ここで $A_1 = 1$ であり、$1 \le i \lt N$ を満たす全ての整数 $i$ について、 $A_i \lt A_{i + 1}$ かつ $A_{i + 1}$ は $A_i$ の倍数です。

この国のある店で、犬のルンルンは $X$ 円の商品を購入するために店員に $y\ (\ge X)$ 円を渡し、店員はお釣りとして $y - X$ 円を返しました。(お釣りが $0$ 円の可能性もあります) このとき、ルンルンも店員もその金額をちょうど渡すのに必要な最小の枚数のコインで受け渡しを行いました。 また、ルンルンが店員に渡したコインのいずれかと同じ種類のコインが店員から返されることはありませんでした。

$X$ が与えられるので、$y$ として考えられる値が何通りあるかを求めてください。

制約

• $1 \le N \le 50$
• $1 = A_1 \lt A_2 \lt A_3 \lt \dots \lt A_N \le 10^{15}$
• $A_{i + 1}$ は $A_i$ の倍数 $(1 \le i \lt N)$
• $1 \le X \le 10^{15}$
• 入力はすべて整数

入力

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

$N$ $X$

$A_1 \hspace{7pt} A_2 \hspace{7pt} A_3 \hspace{5pt} \dots\ \hspace{5pt} A_N$

出力

$y$ として考えられる値が何通りあるかを出力せよ。

3 9
1 5 10

3

$y$ として考えられる値は $9, 10, 14$ です。 例えば、 $y = 14$ のときルンルンは $10$ 円玉 $1$ 枚と $1$ 円玉 $4$ 枚を渡し、店員は $5$ 円玉 $1$ 枚でお釣りを返します。 このとき、ルンルンが渡したどの種類のコインも店員は返していないので条件を満たします。

5 198
1 5 10 50 100

5

$y$ として考えられる値は $198, 200, 203, 208, 248$ です。

4 44
1 4 20 100

4

$y$ として考えられる値は $44, 60, 100, 104$ です。

9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

21