无找零购物(No Change G)

题目描述

Farmer John 到商场购物，他的钱包里有 $K(1\le K\le 16)$ 个硬币，面值的范围是 $[1,10^8]$。

FJ 想按顺序买 $N$ 个物品 $(1\le N\le 10^5)$，第 $i$ 个物品需要花费 $c_i$ 块钱，$(1\le c_i \le 10^4)$。

在依次进行的购买 $N$ 个物品的过程中，FJ 可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果 FJ 支付的硬币面值大于所需的费用，他不会得到任何找零。

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

输入格式

第 $1$ 行两个整数，$K$ 和 $N$。

第 $2$ 行到第 $K+1$ 行每行包含 FJ 的一个硬币的金额。

第 $K+2$ 行到第 $N+K+1$ 行共 $N$ 行，每行包含 FJ 的准备购买的物品的成本。（注：即 $c_i$。）

输出格式

第 $1$ 行：FJ 最终能剩余的最大金额；若无法完成所有购买，则输出 $-1$。

样例输入 #1

3 6
12
15
10
6
3
3
2
3
7

样例输出 #1

12

数据范围

样例说明

FJ 拥有三枚面值分别为 $12$、$15$ 和 $10$ 的硬币。他需要按顺序完成价值 $6$、$3$、$3$、$2$、$3$ 和 $7$ 的购买。

FJ 用 $10$ 面值的硬币支付前两次购买（$6+3$），随后用 $15$ 面值的硬币支付剩余购买（$3+2+3+7$），最终剩下 $12$ 面值的硬币。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

测试点分布

出处：原题链接