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
52
53
54
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORD(i,a,b) for (int i = (b) - 1; i >= (a); --i)
#define REPD(i,n) FORD(i,0,n)

int n, m, a[24], c[100], n2;
int sum[1 << 24];
int been[1 << 24];
int left;
int jj;
int best;

void go() {
	if (jj == best) return;
	if (been[left] & ((1 << (jj + 1)) - 1)) return;
	REPD(ma,n2) {
		ma &= left;
		if (!ma) break;
		if (sum[ma] > c[jj]) continue;
		left ^= ma;
		if (!left)
			best = jj;
		else {
			++jj;
			go();
			--jj;
		}
		left ^= ma;
		if (jj == best) break;
	}
	been[left] |= (1 << jj);
}

int main() {
	scanf("%d%d", &n, &m);
	REP(i,n) scanf("%d", &a[i]);
	REP(j,m) scanf("%d", &c[j]);
	n2 = 1 << n;
	REP(ma,n2) REP(i,n) if (ma & (1 << i)) {
		sum[ma] += a[i];
		if (sum[ma] > 100000000) break;
	}
	sort(c, c + m);
	reverse(c, c + m);
	left = n2 - 1;
	best = m;
	go();
	if (best < m) printf("%d\n", best + 1);
	else printf("NIE\n");
}