[USACO13NOV] No Change G（状态压缩+前缀和）

USACO13NOV No Change G问题解析

题目描述

约翰前往市场采购农场所需物资。他随身携带K枚硬币（1 <= K <= 16），每枚硬币的面值范围为1至100,000,000。他计划按顺序完成N次购物（1 <= N <= 100,000），其中第i次购物所需费用为c(i)单位货币（1 <= c(i) <= 10,000）。在进行这一系列购物时，他可以随时暂停并使用一枚硬币支付自上次付款以来的所有购物费用（所用硬币必须足够支付这些费用）。然而，由于市场上的商家无法提供找零，若约翰使用的硬币面值超过应付金额，他将无法获得任何退款。

请计算约翰在完成所有N次购物后最多能够剩余的金额。若无法完成全部购物，则输出-1。

输入格式

• Line 1: Two integers, K and N.

• Lines 2…1+K: Each line presents the monetary value of one of FJ’s coins.

• Lines 2+K…1+N+K: These N lines include the expenses associated with FJ’s planned purchases.

输出格式

• Line 1: The maximum amount of money FJ ca