题目描述

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

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

输入格式

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

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

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

输出格式

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

样例

输入样例

3 6
12
15
10
6
3
3
2
3
7

输出样例

12