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
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// PA2014, runda 2, Pakowanie
// Andrzej Pezarski

#include <cstdlib>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>


using namespace std;



template <class iter>
long long recGenMin(iter fS, iter lS, iter fX, iter lX, long long c, long long s) {
	long long res=200000000;
	while (fS!=lS) {
		s+=*fS;
		res=min(res, recGenMin(fS+1, lS, fX, lX, c, s));
		
		iter iX=fX;
		while(iX!=lX && (*iX) - s > c) iX++;
		if ((*iX) - s >=0) res=min(res, c- ((*iX) - s));
			  
		s-=*fS;
		res=min(res, recGenMin(fS+1, lS, fX, lX, c, s));
		
		fS++;
	}
	return res;
}



template <class iter>
bool recSubSet(iter fA, iter lA, long long sumA, iter fC, iter lC, long long sumC, iter fS, iter lS, long long sumS, iter fX, iter lX, long long minC) {
	if (sumS>*fC) return false;
//	printf("tutaj %lld\n", minC);
	if (fA==lA) {
//		printf("tutaj3\n");
		if (sumS==0) return false;
//		printf("tutaj4\n");
//		for (auto i=fX; i!=lX; i++) printf("%d ", *i);
//		printf("\n");
//		for (auto i=fS; i!=lS; i++) printf("%d ", *i);
//		printf("\n");
//		printf("%d %lld %lld\n", *fC, sumS, minC);
		if ((*fC)-sumS >= minC) return false;
//		printf("tutaj5\n");
		return recKoszyk(fX+1, lX, sumA-sumS, fC+1, lC, sumC-(*fC));
	}

	*lX=*fA;
	if (recSubSet(fA+1, lA, sumA, fC, lC, sumC, fS, lS, sumS, fX, lX+1, minC)) return true;
//	printf("tutaj8 %d %d\n", lX[-1], *fA);
	
	if (lX[-1]!=*fA) {
		*lS=*fA;
		sumS+=*fA;
		minC=min(minC, (long long) (lX[-1]-*fA));
		minC=min(minC, recGenMin(fS, lS, fX, lX, (*fC)-sumS, *fA));
		if (recSubSet(fA+1, lA, sumA, fC, lC, sumC, fS, lS+1, sumS, fX, lX, minC)) return true;
	}
	return false;
}



template <class iter>
bool recKoszyk(iter fA, iter lA, long long sumA, iter fC, iter lC, long long sumC) {
//	printf("tutaj2\n");
	if (sumA==0) return true;
	if (sumC<sumA) return false;
	int X[25];
	X[0]=300000000;
	int S[25];
	return recSubSet(fA, lA, sumA, fC, lC, sumC, S, S, 0LL, X, X+1, sumC-sumA+1);
}



pair<int, int> tab[1024*1024*16];


int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	
	int A[25];
	long long sumA=0;
	for (int i=0; i<N; i++) {
		scanf("%d", A+i);
		sumA+=A[i];
	}
	sort(A, A+N);
	reverse(A, A+N);
	
	
	int C[125];
	long long sumC=0;
	for (int i=0; i<M; i++) {
		scanf("%d", C+i);
	}
	sort(C, C+M);
	reverse(C, C+M);
	M=min(M, N);
	
	
//	reverse(C, C+M);

	tab[0]=make_pair(0, 0);
	for (int K=1; K<(1<<N); K++) {
		tab[K]=make_pair(M, 0);
	}
	
	for (int K=0; K<(1<<N); K++) {
		if (tab[K].first==M) continue;
		for (int i=0, j=1; i<N; i++, j*=2) {
			if (!(j&K)) {
				auto tmp=tab[K];
				if (C[tmp.first]-tmp.second<A[i]) {
					tmp.first++;
					tmp.second=0;
				}
				tmp.second+=A[i];
				if (C[tmp.first]<tmp.second) tmp.first=M;
				
				tab[j|K]=min(tab[j|K], tmp);
			}
		}
	}
	
	if (tab[(1<<N)-1].first<M) printf("%d\n", tab[(1<<N)-1].first + 1);
	else printf("NIE\n");
	
	
// 	bool ok=false;
// 	for (int i=M-1; i>=0; i--) {
// 		sumC+=C[i];
// 		if ((ok=recKoszyk(A, A+N, sumA, C+i, C+M, sumC))) {
// 			printf("%d\n", M-i);
// 			break;
// 		}
// 	}
// 
// 	if (!ok) printf("NIE\n");
	
	return 0;
}