← 返回题目列表

AtCoder · ttpc2022_b

B. 神奇钱包

中文机器翻译题面 查看原题

配点 : 200 点

問題文

你 X 拥有一个装有 圆的魔法钱包。

对钱包使用魔法后,你可以将钱包里的金额 10 视为 进制字符串并任意重新排列。120 例如, 12 円、 21 円、 102 円、 120 円、 201 円、 210 对装有 圆的魔法钱包使用魔法后,可以将其中的金额 0 变为某个 圆(首位的 会被忽略)。

接下来,你将拥有魔法钱包 N 访问 个商店按顺序前往。 i 第 个商店 (1 ≤ i ≤ N) 有 A_i 圆的商品 1 件出售,如果魔法钱包中有 A_i 元以上,就可以从魔法钱包中支付 A_i 元购买该商品。

魔法可以在任何时候随意使用。你最多可以购买多少商品?

制約

  • 所有输入均为整数
  • 1 \le N \le 100
  • 1 \le X < 10^4
  • 1 \le A_i < 10^4 (1 ≤ i ≤ N)

入力

输入是按以下格式从标准输入给出的。

N X
A_1 A_2 \cdots A_N

出力

打印答案。 来自


入力例 1

2 120
142 90

出力例 1

2

在去第一个商店之前,如果使用魔法将持有的金额变为 120 从日元 201 元,就可以购买商品。此外,此时魔法钱包中有 59 日元剩下的话,可以进一步使用魔法将钱包里的钱变为 95 日元,这样在下一个商店也可以购买商品。最初将钱包里的钱变为 210 日元的话,可以在第一个商店购买商品,但钱包里的钱会变为 68 日元,无法在下一个商店购买商品。请注意,有时可以购买超过


入力例 2

1 119
911

出力例 2

1

X 日元的商品。也可以按


入力例 3

5 1000
900 90 900 9 900

出力例 3

3

0 开头的顺序进行排列。


入力例 4

7 1171
6328 2419 8302 7503 1744 8495 1522

出力例 4

5