Problem Description

In a certain country, there are 20 types of coins in circulation: $1, 10, 100, \ldots, 10^9$ yen coins and $5, 50, 500, \ldots, 5 \times 10^9$ yen coins.

Tempura-kun went to a supermarket to buy fruits. There are $N$ types of fruits sold, one each, with prices $A_1, A_2, \ldots, A_N$ yen respectively.

Tempura-kun decided to buy $K$ of these fruits. Find the minimum number of coins needed to exactly pay the total amount. Note that Tempura-kun has an ample supply of all types of coins.

Input Format

The input is given from the standard input in the following format:

$N\ K$ $A_1\ A_2\ \ldots\ A_N$

Output Format

Output the minimum number of coins needed in one line.

Sample Input and Output

Sample Input #1

3 2
25 29 62

Sample Output #1

5

Sample Input #2

3 1
10000 2 3

Sample Output #2

1

Sample Input #3

10 3
1415 9265 3589 7932 3846 2643 3832 7950 2884 1971

Sample Output #3

5

Notes/Hints

Constraints

• $1 \le N \le 32$
• $1 \le K \le \min(N, 6)$
• $1 \le A_i \le 10^8$
• All inputs are integers

Sample Explanation 1

Buying the first and second items totals to 54 yen, which can be paid with 1 coin of 50 yen and 4 coins of 1 yen, totaling 5 coins. This is the minimum case.

见题面 Input 部分

见题面 Output 部分