← 返回题目
题库练习 不改变
← 上一题 下一题 →

A2213 | 不改变

来源USACO / 2013
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

约翰到商场购物，他的钱包里有K(1 <= K <= 16)个硬币，面值的范围是1..100,000,000。

约翰想按顺序买 N个物品(1 <= N <= 100,000)，第i个物品需要花费c(i)块钱，(1 <= c(i) <= 10,000)。

在依次进行的购买N个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

请计算出在购买完N个物品后，约翰最多剩下多少钱。如果无法完成购买，输出-1

输入格式

* 第 1 行：两个整数，K 和 N。

* 第 2..1+K 行：每行包含 FJ 的一枚硬币的金额。

* 第 2+K. 行。1+N+K：这 N 行包含 FJ 打算购买的成本。

输出格式

* 第 1 行：FJ 最终可以获得的最大金额，如果 FJ 无法完成所有购买，则为 -1。

输入输出样例

输入 #1
3 6 
12 
15 
10 
6 
3 
3 
2 
3 
7
输出 #1
12
C++ 编辑器
输入
输出