硬币的支付方式

题目描述

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$ 可能有多少种取值。

输入格式

输入按以下格式从标准输入给出：

$N$ $X$
$A_1$ $A_2$ $A_3$ $\dots$ $A_N$

输出格式

输出 $y$ 可能的取值数量。

样例

3 9
1 5 10

3

$y$ 可能的取值为 $9, 10, 14$。

例如，当 $y = 14$ 时，露露支付 $1$ 枚 $10$ 日元硬币和 $4$ 枚 $1$ 日元硬币，店员用 $1$ 枚 $5$ 日元硬币找零。

此时，店员没有找给露露任何露露支付过的那种硬币，所以满足条件。

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

数据范围

• $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}$
• 输入均为整数