题目描述

$K$ 个硬币，要买 $N$ 个物品。

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

输入格式

第一行两个整数 $K,N$。

接下来的 $K$ 行，每行一个整数，表示这枚硬币的面值。

接下来的 $N$ 行，每行一个整数，表示这个物品的价格。

输出格式

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

3 6
12
15
10
6
3
3
2
3
7

12 

样例说明 1

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

他可以用面值为 $10$ 的硬币购买前两个物品，然后用面值 $15$ 的硬币购买剩下的物品。这样它可以剩下一枚面值 $12$ 的硬币。

数据规模与约定

对于 $100\%$ 的数据，$1\leq K\leq 16$，$1\leq N\leq 10^5$，每枚硬币的面值在范围 $1\sim 10^8$ 内，$1\leq c_i\leq 10^4$。

题目来源

Gold