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
#include <stdio.h>
#include <algorithm>
#include <functional>

using namespace std;

const int MaxN = 24,
          MaxM = 150,
          MaxSiz = (1<<MaxN),
          Infty = 1010101010;

int N, M;
int items[MaxN], iitems[MaxSiz], bags[MaxM];
int nextBit[MaxSiz];


struct State {
	int numLast, freeLast;
	
	State(int num=Infty, int f=Infty) : numLast(num), freeLast(f) {}
	
	bool operator<(const State &S) const {
		if(numLast == S.numLast){
			return freeLast > S.freeLast;
		} else {
			return numLast < S.numLast;
		}
	}
	State operator-(const int t) const {
		if(freeLast >= t)
			return State(numLast, freeLast-t);
		else {
			int siz = bags[numLast+1] - t;
			if(siz >= 0)
				return State(numLast+1, siz);
			else
				return State(M, Infty);
		}
	}
};

State S[MaxSiz];


void make_nextbit(){
	nextBit[0] = 0;
	
	unsigned val = 2;
	int num = 0;
	
	for(int i = 1; i < (1<<N); i++){
		if(i & val){ val *= 2; num++; }
		nextBit[i] = num;
	}
}

void input(){
	scanf("%d%d", &N, &M);
	
	for(int i = 0; i < N; i++){
		scanf("%d", &items[i]);
		iitems[1<<i] = items[i];
	}
		
	for(int i = 0; i < M; i++)
		scanf("%d", &bags[i]);
	for(int i = M; i < MaxM; i++)
		bags[i] = Infty;
	
	sort(bags, bags+M, greater<int>());
	sort(items, items+N, less<int>());
}


void process(){
	S[0] = State(0, bags[0]);
	
	for(unsigned mask = 1; mask < (1<<N); mask++){
		/*for(int i = 0; i < N; i++){
			if(mask & (1<<i)){
				S[mask] = min(S[mask], S[mask ^ (1<<i)] - items[i]);
				//break;
			}
		}*/
		unsigned m = mask;
		
		while(m){
			int i = nextBit[m];
			
			S[mask] = min(S[mask], S[mask ^ (1<<i)] - items[i]);
			m ^= (1<<i);
		}
	}
}

void output(){
	unsigned lastMask = (1<<N)-1;
	
	if(S[lastMask].numLast >= M)
		printf("NIE\n");
	else
		printf("%d\n", S[lastMask].numLast+1);
}


int main(){
	input();
	make_nextbit();
	process();
	output();
}