OI题库

【题目描述】

    FJ正在市场上为他的农场采购日用品，他口袋里有K(1<=K<=16)个硬币，每一个硬币的面值均在1～1,000,000,000之间。FJ有一个包含N(1<=N<=100,000)种待购物品的序列清单，其中第i种物品需要的钱数为c(i)，（1<=c(i)<=10,000），在购物的过程中，他随时可以停下来用一枚硬币付一次钱，每次付钱的对象为从上次付钱之后至当前所有物品价值和（当然，他所付的硬币面值也必须足够大），不巧的是，市场上的商户们都没有零钱了，因此如果FJ给的硬币面值大于所购物品价值，他也不会得到找零！

   请计算FJ完成N件物品的购物后，所能剩下的最大钱数。如果他无法买到所有物品，输出-1。

【输入格式】

第1行：两个整数K，N；

第2～K+1行：每行为一个硬币面值；

第K+2～N+K+1行：这N行为FJ所要购买的N件物品的价值。

【输出格式】

一行，即结束购物后FJ所剩余的最大钱数，输出-1表示他无法完成购物。

【样例输入】

3 6
12
15
10
6
3
3
2
3
7

【样例输出】

12
输出解释：
FJ花费面值为10的硬币购买前两件物品，然后花费面值为15的硬币购买剩余的4样物品，最后剩余一枚面值为12的硬币。

【提示】

在此键入。

【来源】

USACO 2013 November Contest, Gold