In a distant country, the currency system uses banknotes with denominations of $500, 100, 50, 10, 5, 1$.

A shop sells $n$ items, where the $i$-th item has a price of $a_i$, and there is only one of each item.

You have $X$ units of currency, and the banknotes you hold are the minimum set required to represent $X$.

You can perform several operations. Each operation consists of the following steps in order:

• Select a subset of items that have not been purchased yet.
• Pay for them using some of the banknotes you currently hold. You may overpay, but you cannot underpay.
• The shop gives you change using the minimum number of banknotes. The shop has an infinite supply of banknotes.

You want to maximize the number of $1$-unit banknotes you hold after performing any number of operations. Find this maximum number.

Input

The first line contains two positive integers $n$ and $X$.

The second line contains $n$ positive integers $a_1, \dots, a_n$.

Output

Output a single non-negative integer representing the maximum number of $1$-unit banknotes you can hold.

Examples

Input 1

5 57
9 14 31 18 27

Output 1

8

Note 1

The banknotes you hold are $50+5+1+1$.

First, purchase the 3rd item, pay $50$, and receive $10+5+1+1+1+1$ in change. Alternatively, you could pay $50+5$ and receive $10+10+1+1+1+1$ in change.

Then, purchase the 4th item, pay $10+5+5$ (or $10+10$ in the second case), and receive $1+1$ in change.

At this point, you have exactly $8$ banknotes of denomination $1$.

Input 2

4 50
11 11 11 11

Output 2

12

Constraints

This problem uses subtask-based testing.

For all test cases, $1 \le n \le 10^5$, $1 \le X \le 10^{14}$, and $1 \le a_i \le X$.