约翰带着 N 头奶牛在超市买东西，现在他们正在排队付钱，排在第 i 个位置的奶牛需要支付 Ci 元。今天说好所有东西都是约翰请客的，但直到付账的时候，约翰才意识到自己没带钱，身上只有 K 张消费卡，第 i 张卡里有 Vi 元余额。

问题是，这些消费卡都是一次性的，它们可以被收银机读取，但如果卡一旦离开了收银机，卡里 的余额就会归零，而且超市也不负责找零！奶牛的队伍很长，不可能再调整她们的位置了，所以一张 卡只能支付一段连在一起的账单。而且，一张账单只能用一张消费卡支付，超市的系统不接受用两张 或以上的卡支付一笔账单。

约翰的问题就是按照什么样的顺序来使用这些消费卡，才能让他能为所有的奶牛买单，而且使得 剩余的消费卡的余额之和最大呢？

? 第一行：两个整数 K 和 N ，1 ≤ K ≤ 16, 1 ≤ N ≤ 10^5

? 第二行到第 K + 1 行：第 i + 1 行有一个整数 Vi，1 ≤ Vi ≤ 10^9

? 第 K + 2 行到第 K + N + 1 行：第 i + K + 1 行有一个整数 Ci，1 ≤ Ci ≤ 10^4

单个整数：表示约翰买完所有奶牛的单之后，最多还能剩多少余额，如果他带的卡根本没有办 法支付所有的账单，输出 ?1。

#include<cstdio>
#include<iostream>
using namespace std;
int a[100010],g[1<<16],f[1<<16],w[20],ans=-1;
int i,j,n,k,inf,l,r,mid;
int find(int st,int x)
{
	l=st;r=n+1;a[n+1]=1e9;
	int ans;
	while(l+1<r)
	{
		mid=(l+r)>>1;
		if(a[mid]-a[st]>x)r=mid;
		else l=mid;
	}
	return l;
}
int main()
{
//	freopen("xx.in","r",stdin);
	scanf("%d%d",&k,&n);
	for(i=1;i<=k;g[0]+=w[i],++i)
	scanf("%d",&w[i]);
	for(i=1;i<=n;a[i]+=a[i-1],++i)
	scanf("%d",&a[i]);
	inf=(1<<16)-1;
	for(i=1;i<=inf;++i)
	{
		for(j=1;j<=16;++j)
		if(i&1<<j-1)
		{
			int c=find(f[i-(1<<j-1)],w[j]);
			if(c>f[i]||(c==f[i]&g[i-(1<<j-1)]-w[j]>g[i]))
			f[i]=c,g[i]=g[i-(1<<j-1)]-w[j];
			if(f[i]==n&g[i]>ans)
			ans=g[i];
		}
	}
	printf("%d",ans);
}