問題文

ある国では 1,\ 10,\ 100,\ldots ,10^{9} 円硬貨および 5,\ 50,\ 500,\ldots ,5\times 10^{9} 円硬貨の 20 種類の硬貨が流通しています。

てんぷら君は果物を買いにスーパーマーケットに行きました。そこには N 種類の果物が 1 つずつ売られており、値段はそれぞれ A_1, A_2,\ldots, A_N 円です。

てんぷら君はこの中から K 個を選んで買うことにしました。合計金額をちょうど支払うために必要な硬貨の枚数として考えられる最小の枚数を求めてください。なお、てんぷら君はすべての硬貨を十分たくさん持っているものとします。

制約

• 1\le N\le 32
• 1\le K\le min(N, 6)
• 1\le A_i\le 10^8
• 入力はすべて整数

入力例 1

3 2
25 29 62

出力例 1

5

1 つめの商品と 2 つめの商品を購入すると合計金額は 54 円で、50 円硬貨 1 枚と 1 円硬貨 4 枚の合計 5 枚で支払うことができます。この場合が最小です。

入力例 2

3 1
10000 2 3

出力例 2

1

入力例 3

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

出力例 3

5