bzoj#P3312. [USACO2013 Nov] No Change

[USACO2013 Nov] No Change

题目描述

KK 个硬币,要买 NN 个物品。

给定买的顺序,即按顺序必须是一路买过去,当选定买的东西物品序列后,付出钱后,货主是不会找零钱的。现希望买完所需要的东西后,留下的钱越多越好,如果不能完成购买任务,输出 1-1

输入格式

第一行两个整数 K,NK,N

接下来的 KK 行,每行一个整数,表示这枚硬币的面值。

接下来的 NN 行,每行一个整数,表示这个物品的价格。

输出格式

一行一个整数,表示买完东西后剩下的最多的钱。若不能完成购买任务,输出 1-1

3 6
12
15
10
6
3
3
2
3
7
12 

样例说明 1

Farmer John 有 33 枚硬币,面值为 12,15,1012,15,10. 他必须按照顺序购买价值分别为 6,3,3,2,3,76,3,3,2,3,7 的物品。

他可以用面值为 1010 的硬币购买前两个物品,然后用面值 1515 的硬币购买剩下的物品。这样它可以剩下一枚面值 1212 的硬币。

数据规模与约定

对于 100%100\% 的数据,1K161\leq K\leq 161N1051\leq N\leq 10^5,每枚硬币的面值在范围 11081\sim 10^8 内,1ci1041\leq c_i\leq 10^4

题目来源

Gold