bzoj#P3312. [USACO2013 Nov] No Change
[USACO2013 Nov] No Change
题目描述
个硬币,要买 个物品。
给定买的顺序,即按顺序必须是一路买过去,当选定买的东西物品序列后,付出钱后,货主是不会找零钱的。现希望买完所需要的东西后,留下的钱越多越好,如果不能完成购买任务,输出 。
输入格式
第一行两个整数 。
接下来的 行,每行一个整数,表示这枚硬币的面值。
接下来的 行,每行一个整数,表示这个物品的价格。
输出格式
一行一个整数,表示买完东西后剩下的最多的钱。若不能完成购买任务,输出 。
3 6
12
15
10
6
3
3
2
3
7
12
样例说明 1
Farmer John 有 枚硬币,面值为 . 他必须按照顺序购买价值分别为 的物品。
他可以用面值为 的硬币购买前两个物品,然后用面值 的硬币购买剩下的物品。这样它可以剩下一枚面值 的硬币。
数据规模与约定
对于 的数据,,,每枚硬币的面值在范围 内,。
题目来源
Gold