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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const char inf = 100+9;
const int mx  = (1<<24) + 9;

char a[mx], b[mx];

int main(){
	int n, m;
	cin >> n >> m;
	
	vector<unsigned int> rze(n), ple(m);
	for(int i = 0; i < n; ++i) cin >> rze[i]; 
	for(int i = 0; i < m; ++i) cin >> ple[i];
	
	sort(ple.begin(), ple.end(), greater<unsigned int>());
	
	char * t1 = a;
	char * t2 = b;
	memset(t2, inf, (1<<n) + 5);
										
	for(int k = min(m,n)-1; k >= 0; k--){
		memset(t1, inf, (1<<n) + 5);
		
		vector<int> t(n+1);
		t[0] = 1;
		while(!t.back()){
			int c = 0, r = 0;
			unsigned int s = 0;
			for(int i = 0; i < t.size()-1; ++i){
				if(t[i] == 1) s += rze[i];
				if(t[i] == 2) r |= 1 << i;
				if(t[i]) c |= 1 << i;
			}									
			if(s <= ple[k]){
				if(r == 0) t1[c] = 1;
				else t1[c] = min(int(t1[c]), 1 + int(t2[r]));
			}
			
			int x = 0;
			while(t[x] == 2){ t[x] = 0; x++; }
			t[x]++;
		}	
		swap(t1,t2);
	}
	
	int wsz = (1<<n)-1;
	
	if(t2[wsz] == inf) cout << "NIE\n"; 
	else cout << int(t2[wsz]) << "\n";
	
	return 0;
}