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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<algorithm>
#include<functional>
const int N = 24;
const int Nsubsets = 1 << N;
const int M = 100;
struct SubsetData{
	char minBackpacks;
	int minContentOfLast;
	SubsetData():minBackpacks(N + 1), minContentOfLast(0){};
} DP[Nsubsets];

int itemMasses[N];
int maxLoads[M];
int singletons[N];

void printSet(int s, int n){
	printf("{");
	bool first = true;
	for(int i = 0; i < n - 1; i++)
		if(s & singletons[i]){
			printf(first ? "%d" : ", %d", i);
			first = false;
		}
	printf("}");
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	
	for(int i = 0; i < n; i++){
		scanf("%d", &itemMasses[i]);
		singletons[i] = 1 << i;
	}
	std::sort(itemMasses, itemMasses + n);
	for(int i = 0; i < m; i++)
		scanf("%d", &maxLoads[i]);
	std::sort(maxLoads, maxLoads + m, std::greater<int>());
	
	for(int i = 0; i != n; ++i){
		if(itemMasses[i] > maxLoads[0]){
			printf("NIE\n");
			return 0;
		}
		DP[singletons[i]].minBackpacks = 1;
		DP[singletons[i]].minContentOfLast = itemMasses[i];
	}
	for(int s = 1; s < (1 << n) - 1; ++s){
		//printSet(s, n);
		//printf("\t - %d %d\n", DP[s].minBackpacks, DP[s].minContentOfLast);
		int i = 0;
		int newContent;
		for(; i !=  n && (newContent = DP[s].minContentOfLast + itemMasses[i]) <= maxLoads[DP[s].minBackpacks - 1]; ++i){
			if(!(s & singletons[i])){
				int si = s | singletons[i];
				if(DP[s].minBackpacks < DP[si].minBackpacks){
					DP[si].minBackpacks = DP[s].minBackpacks;
					DP[si].minContentOfLast = newContent;
				}
				if(DP[s].minBackpacks == DP[si].minBackpacks && newContent < DP[si].minContentOfLast)
					DP[si].minContentOfLast = newContent;
			}
		}
		for(; i !=  n && (newContent = itemMasses[i]) <= maxLoads[DP[s].minBackpacks]; ++i){
			if(!(s & singletons[i])){
				int si = s | singletons[i];
				if(DP[s].minBackpacks + 1 < DP[si].minBackpacks){
					DP[si].minBackpacks = DP[s].minBackpacks + 1;
					DP[si].minContentOfLast = newContent;
				}
				if(DP[s].minBackpacks + 1 == DP[si].minBackpacks && newContent < DP[si].minContentOfLast)
					DP[si].minContentOfLast = newContent;
			}
		}
	}
	if(DP[(1 << n) - 1].minBackpacks > n)
		printf("NIE\n");
	else
		printf("%d\n", DP[(1 << n) - 1].minBackpacks);
}