← 返回题目列表

AtCoder · kupc2021_f

F. 一日元硬币

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

配点 : 300 点

問題文

KUPC国家目前使用的硬币与日本相同。 500 、 100 、 50 、 10 、 5 、 1 日元硬币 6 类型。

KUPC国家唯一的商店有 N 产品已售出, i 该商品的价格是 A_i 是日元。 另外,您可以将硬币数量设置为最小值。 X 我有日元。

您现在可以在商店自由购物。 在购物时,您可以根据需要多次重复下面定义的结账。

  • 记账是指选择若干商品并支付超过总金额的费用来购买。
  • 此时,支付金额与所选商品总金额之间的差额将作为零钱退回,这样就会退回最少数量的硬币。
  • 每个产品都是 由于只有 1 件,因此您无法通过购物购买多件同一商品。

你 我想重新排列 1 我喜欢日元硬币,所以我想收集尽可能多的硬币。 1 我想收集日元硬币。 购物完成后即可获得 1 找出日元硬币的最大数量。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq X \leq 10^{14}
  • 1 \leq A_i \leq 10^9
  • 所有输入均为整数。

入力

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

N X
A_1 A_2 \ldots A_N

出力

购物完成后即可领取 1 日元硬币最大数量 1 行。


入力例 1

5 57
27 18 31 9 14

出力例 1

8

入力例 2

4 50
11 11 11 11

出力例 2

12