配点 : 300 点
問題文
在某些国家/地区 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
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N\ K A_1\ A_2\ \ldots\ A_N
出力
所需的最低硬币数量 在 1 行输出。
入力例 1
3 2 25 29 62
出力例 1
5
1 与下一个产品 2 如果您购买第二件商品,总金额将为 54 以日元计算,50 円硬貨 1 和 1 円硬貨 4 总计 您可以用 5 件付款。这种情况是最少的。
入力例 2
3 1 10000 2 3
出力例 2
1
1 最好购买价值10,000日元的物品。
入力例 3
10 3 1415 9265 3589 7932 3846 2643 3832 7950 2884 1971
出力例 3
5