1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <cstdio>
using namespace std;

typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)

#define ST first
#define ND second

const int MAXN = 24;
const int MAXM = 110;

int n, m;
int W[MAXN], C[MAXM];
PII dp[(1<<MAXN)+3];

int main(int argc, char *argv[]) {
	scanf("%d %d", &n, &m);
	REP(i,n) scanf("%d", W+i);
	REP(i,m) scanf("%d", C+i);
	sort(W, W+n, greater<int>());
	sort(C, C+m, greater<int>());
	if(n < m) {
		REP(i,m-n) C[n+i] = 0;
		m = n;
	}
	dp[0] = {0, -C[0]};
	for(int mask=1;mask<(1<<n);mask++)
	{
		PII r(m, 0);
		for(int i=0;(1<<i)<=mask;i++)
		{
			if(!(mask & (1<<i))) continue;
			PII sub = dp[mask ^ (1<<i)];
			PII t(sub.ST+1, -C[sub.ST+1]+W[i]);
			if(t.ND > 0) t.ST = m;
			if(sub.ND <= -W[i] && (sub.ST < t.ST || (sub.ST == t.ST && sub.ND+W[i] < t.ND)))
				t = PII(sub.ST, sub.ND+W[i]);
			if(t.ST < r.ST || (t.ST == r.ST && t.ND < r.ND))
				r = t;
		}
		if(r.ND > 0) r = PII(m, 0);
		dp[mask] = r;
	}
	int res = dp[(1<<n)-1].ST;
	if(res == m) printf("NIE\n");
	else printf("%d\n", res+1);
	return 0;
}