题目描述

农夫约翰在市场上为他的农场购买供应品。他的口袋里有$\red{K}$个硬币$\red{(1 <= K <= 16)，}$每个硬币的值在$\red{1..100,000,000}$之间。$\red{FJ}$想要进行$\red{N}$次购买$\red{(1 <= N <= 100000)}$的序列，其中第$\red{i}$次购买花费$\red{c(i)}$单位 的钱$\red{(1 <= c(i) <= 10000)}$。当他进行这一系列购买时，他可以定期停下来，用一枚硬币支付自上次付款以来的所有购买$\red{(}$当然，他使用的一枚硬币必须足够大，足以支付所有这些$\red{)}$。

不幸的是，市场上的摊贩没有零钱了，所以每当$\red{FJ}$使用比他欠的钱更大的硬币时，他很遗憾地没有收到零钱! 请计算$\red{FJ}$依次完成$\red{N}$次购买后所能获得的最大金额。输出$\red{-1，}$如果$\red{FJ}$不可能完成他所有的购买。 约翰到商场购物，他的钱包里有$\red{K(1 <= K <= 16)}$个硬币，面值的范围是$\red{1..100,000,000}$。 约翰想按顺序买 $\red{N}$个物品$\red{(1 <= N <= 100,000)，}$第$\red{i}$个物品需要花费$\red{c(i)}$块钱，$\red{(1 <= c(i) <= 10,000)}$。 在依次进行的购买$\red{N}$个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开 始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。 请计算出在购买完$\red{N}$个物品后，约翰最多剩下多少钱。如果无法完成购买，输出$\red{-1}$

输入格式

第一行:两个整数，$\red{K}$和$\red{N}$。

第$\red{2 . .1+K:}$每一行包含一个$\red{FJ}$的硬币的金额。

第$\red{2 + K}$行. .$\red{1+N+K:}$这$\red{N}$条线包含$\red{FJ}$打算购买的成本。

输出格式

第一行:$\red{FJ}$最终可以获得的最大金额，或者$\red{-1，}$如果$\red{FJ}$不能完成他所有的购买。

样例

输入样例

3 6
12
15
10
6
3
3
2
3
7

输出样例

12