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
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <cstring>
#include <list>
#include <iostream>
#include <cassert>
using namespace std;
#define FOR(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i <= n; i++)
#define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)
#define frs first
#define sec second
#define psh push_back
#define mkp make_pair
#define MIN(a,b) (a < b ? a : b)
typedef long long LL;
typedef long double LD;

const int INF = 2147483646;
const int MAX_MASK = (1 << 24);
const int MAX_M = 110, MAX_N = 25;

int n,m, FINISH;
int D[MAX_MASK];
int C[MAX_M], A[MAX_N];
vector<int> V[MAX_N];
bool NM[MAX_MASK], Vis[MAX_MASK];

char *bitmask(int a) {
	char* r = (char*)malloc(10);

	int c = 0;
	while(a) {
		r[c] = (a & 1) + '0';
		c++;
		a >>= 1;
	}
	r[c] = '\0';
	return r;
}

int solve() {
	int nmsk;
	vector<int> newV[MAX_N];
	for(int i = 1; i <= n; i++) {
//		memset(D, 0x7F, sizeof(D)); 
		FOR(j,n+1) for(auto mask: V[j]) {
			D[mask] = 0;
		}

		FOR(j,n+1) for(auto mask: V[j]) {
			if(mask == FINISH) return i;
			
			FOR(l,n) {
				if((mask & (1 << l)) == 0) {
					nmsk = mask | (1 << l);
					D[nmsk] = MIN(D[nmsk], D[mask] + A[l]);
					if(D[nmsk] <= C[i]) {
						NM[mask] = true;
						if(!Vis[nmsk]) {
							Vis[nmsk] = true;
							V[j + 1].psh(nmsk);
						}
					}
				}
			}

			if((NM[mask] == false) && (D[mask] != 0))
				newV[j].psh(mask);

			D[mask] = INF;
		}

		FOR(j, n+1) {
			V[j].swap(newV[j]);
			newV[j].clear();
		}
	}

	return -1;
}

int main() {
	memset(D, 0x7F, sizeof(D));
	
	scanf("%d%d", &n, &m);
	FOR(i,n) scanf("%d", &A[i]);
	REP(i,m) scanf("%d", &C[i]);
	sort(C+1, C + 1 + m, greater<int>());
	FINISH = (1 << n) - 1;

	V[0].psh(0);
	int ans = solve();
	if(ans == -1) printf("NIE\n");
	else printf("%d\n", ans);
}