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
55
56
57
58
59
60
61
62
#include<cstdio>
#include<algorithm>
using namespace std;

int *T;
int I[30], B[105];
int n,m;

//O(2^n*m)
void find_best(int mask){
	int bestB = m, bestF = 0, tm = mask;
	while(true){
		int z = __builtin_ffs(tm)-1;
		if(z == -1)break;
		tm ^= (1<<z);

		int v = mask ^ (1<<z);
		int a = T[2*v], b = T[2*v+1];
		if(a < m){
			if(b+I[z]>B[a]){
				a++;
				b = I[z];
			}else b+=I[z];

			if((a < bestB || (a == bestB && b < bestF))&&B[a]>=b){
				bestB = a;
				bestF = b;
			}
		}
	}

	T[2*mask] = bestB;
	T[2*mask+1] = bestF;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++)scanf("%d",&I[i]);
	for(int i=0;i<m;i++)scanf("%d",&B[i]);

	sort(I,I+n);
	sort(B,B+m,std::greater<int>());

	T = new int[2*(1<<n)];
	for(int i=0;i<(1<<n);i++)
		T[2*i] = -1;
	
	//empty asociation
	T[0] = 0; T[1] = 0;

	int v = (1<<n)-1;
	for(int i=1;i<=v;i++)
		find_best(i);
	
	find_best(v);
	if(T[2*v] == m)
		printf("NIE\n");
	else
		printf("%d\n",T[2*v]+1);

	return 0;
}