该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

约翰到商场购物，他的钱包里有$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$.

第二行，$K$ 个整数，表示硬币面额

第二行，$N$ 个整数，表示物品花费

输出格式

一个整数，表示最大剩余硬币总额，如果无法完成购买，输出-1

样例 #1

样例输入 #1

3 6 
12 15 10 
6 3 3 2 3 7

样例输出 #1

12

提示

10买前两个, 15买剩下的，还剩12