问题描述

在一个国家里，有 $20$ 种硬币在流通，这些硬币的面值分别是 $1,\\ 10,\\ 100,\\ldots ,10^{9}$ 日元和 $5,\\ 50,\\ 500,\\ldots ,5\\times 10^{9}$ 日元。

Tempura君去超市买水果。超市里有 $N$ 种水果，每种水果只卖一颗，价格分别是 $A_1, A_2,\\ldots, A_N$ 日元。

Tempura君决定从这些水果中选择 $K$ 种来购买。请计算出为了支付总金额，所需的最小硬币数量。假设Tempura君有足够多的硬币。

约束条件

• $1\\le N\\le 32$
• $1\\le K\\le min(N, 6)$
• $1\\le A_i\\le 10^8$
• 输入均为整数

输入

输入以以下格式从标准输入中给出。

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

输出

输出为所需的最小硬币数量，以一行形式输出。

输入例子 1

3 2
25 29 62

输出例子 1

5

购买第一个商品和第二个商品的总金额是 $54$ 日元，可以用一枚 $50$ 日元硬币和四枚 $1$ 日元硬币来支付，总共 $5$ 枚硬币。这种方式是最少的。

输入例子 2

3 1
10000 2 3

输出例子 2

1

购买 $1$ 万日元的商品是最优选择。

输入例子 3

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

输出例子 3

5