题目描述

约翰到商场购物，他的钱包里有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可以结束的最大金额，或者-1如果FJ不能完成他的所有购买。

3 6 
12 
15 
10 
6 
3 
3 
2 
3 
7

12

提示

FJ有3枚硬币，价值分别为12、15和10。他必须按照价值6、3、3、2、3和7的顺序进行购买。 FJ在前两次购买中花费了他的10个单位硬币，然后在剩余的购买中花费15个单位硬币。这给他留下了12个单位的硬币。