J4 实践-1 硬币问题3

题目描述

家里的冰淇淋又吃完了，于是小喵来到了超市补充存货。这次他带了 $N$ 种面值为 $A_1,A_2,\ldots,A_N$ 的钞票在钱包中，而且对于每种面额 $A_i$ ，都是 $A_{i-1}$ 的倍数，且面额大于 $A_{i-1}$ 。

这次小喵共购买了 $X$ 元的冰淇淋，巧的是，收银员找零柜中的钞票面额与小喵的一样。请你帮小喵找到一种支付方式，使得付给收银员的钞票张数和收银员找零的钞票张数之和最少（假设小喵和收银员每种面值的钞票都足够多）。

输入格式

共 $2$ 行： 第一行两个整数 $N,X$ ，表示钞票的面值数量和冰淇淋的价格； 第二行 $N$ 个整数 $A_i$ ，依次表示第 $i$ 种钞票的面值。

输出格式

一行一个整数，输出最少的付款钞票数量和找零钞票数量之和。

样例输入1

3 87
1 10 100

样例输出1

5

样例1解析

给一张 $100$ 元，找零 $1$ 张 $10$ 元和 $3$ 张 $1$ 元，共 $5$ 张钞票为最少的数量。

样例输入2

2 49
1 7

样例输出2

7

样例输入3

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

样例输出3

233

数据范围

对于 $100 \%$ 的数据：$1\leq N\leq 60$，$1\leq X\leq 10^{18}$，$1=A_1<\ldots<A_N\leq 10^{18}$ ，保证 $A_i$ 是 $A_1,A_2,\ldots,A_i-1$ 的倍数。