← 返回题目列表

AtCoder · cpsco2019_s1_c

C. 硬币

中文机器翻译题面 查看原题

配点 : 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