[USACO13NOV] No Change G

题目描述

约翰到商场购物，他的钱包里有 $K$ 个硬币，每个硬币的面值 $A_i$。

约翰想按顺序买 $N$ 个物品 ，第 $i$ 个物品需要花费 $B_i$ 块钱。

在依次进行的购买 $N$ 个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币。

支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。 不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。

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

输入格式

第一行两个整数 $K$ ， $N$ ($1 \le K \le 16，1 \le N \le 10^5$) .

下来 $K$ 个整数 $A_i$ ($1 \le A_i \le 10^9$).

下来 $N$ 个整数 $B_i$ ($1 \le B_i \le 10^4$).

输出格式

一个整数，即约翰最多剩下多少钱。若无法垢面所有物品，则输出 $-1$

样例 #1

样例输入 #1

3 6 
12 
15 
10 
6 
3 
3 
2 
3 
7

样例输出 #1

12

提示

FJ has 3 coins of values 12, 15, and 10. He must make purchases in sequence of value 6, 3, 3, 2, 3, and 7. FJ spends his 10-unit coin on the first two purchases, then the 15-unit coin on the remaining purchases. This leaves him with the 12-unit coin.