시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 74 | 32 | 22 | 39.286% |
The Flatland currency system uses coins of 500, 100, 50, 10, 5, and 1 Flatland yen.
At the shop in the Flatland airport, there are $N$ bottles of milkohol on sale; the $i$-th bottle costs $a_i$ yen. Note that there are exactly $N$ bottles, so you can buy each bottle no more than once.
You have $X$ flatland yen, and you noticed that the number of coins you have is minimal possible between all representations of $X$.
In the shop, you can do the following sequence of actions any number of times:
You promised your friends 1-yen coins as souvenirs. Find the maximum number of 1-yen coins that you can collect in this shop.
The first line of input contains two integers $N$ and $X$ ($1 \le N \le 10^5$, $1 \le X \le 10^{14}$): the number of bottles in the shop and the number of Flatland yens you have, respectively. The second line contains $N$ integers $A_1, A_2, \ldots, A_N$ ($1 \le A_i \le 10^9$): the prices of the bottles in the shop.
Print one integer: the maximum number of 1-yen coins you may have after visiting the shop.
5 57 9 14 31 18 27
8
4 50 11 11 11 11
12