Public Judge

pjudge

Time Limit: 2 s Memory Limit: 1024 MB Total points: 100 Hackable ✓

# 21689. 【NOIP Round #2】找零

Statistics

在一个遥远的国家用着这样一套货币系统:纸币的面额分别是 $500,100,50,10,5,1$ 。

在一家商店里有 $n$ 个物品出售,第 $i$ 个物品的价格是 $a_i$ ,每样物品只有一个。

你有 $X$ 元钱,并且手上的纸币恰好是能表示出 $X$ 的方案里最少的一组。

你可以进行若干次操作,每次顺序执行每一步:

  • 选择若干个没买过的物品。
  • 用你手上的一些纸币付钱。可以多付,不能少付。
  • 商店用最少的纸币给你找零。商店的纸币是无限的。

你希望在进行若干次操作之后最大化手上面额为 $1$ 的纸币数量。求出最大数量。

输入格式

第一行,两个正整数 $n,X$ 。

第二行 $n$ 个正整数 $a_1,\cdots,a_n$ 。

输出格式

输出一行一个非负整数,表示最终手上面额为 $1$ 的纸币数量的最大值。

样例一

input

5 57
9 14 31 18 27

output

8

explanation

手上的纸币是 $50+5+1+1$ 。

先购买第 $3$ 个物品,付款 $50$ ,找零 $10+5+1+1+1+1$ 。这里也可以付款 $50+5$ ,找零 $10+10+1+1+1+1$ 。

再购买第 $4$ 个物品,付款 $10+5+5$ (第二种情况则是 $10+10$),找零 $1+1$ 。

此时手上恰有 $8$ 张面额为 $1$ 的纸币。

样例二

input

4 50
11 11 11 11

output

12

数据范围与提示

本题采用子任务捆绑测试。

对于所有数据,保证 $1\le n\le 10^5, 1\le X\le 10^{14}, 1\le a_i\le X$ 。

测试点编号 $n\le$ $X\le$ 分值
$1$ $8$ $10^8$ $20$
$2$ $15$ $90$ $20$
$3$ $200$ $10^{4}$ $20$
$4$ $3000$ $10^{14}$ $20$
$5$ $10^5$ $20$