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
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long slng;
#define MAXN 24
#define MAXM 107

//#define DEBUG(...) printf(__VA_ARGS__); fflush(stdout)
//#define VDEBUG(...) printf(__VA_ARGS__); fflush(stdout)
#define VDEBUG(...) 
#define DEBUG(...) 

bool slng_inv(const slng &a, const slng &b) {
	return a > b;
}

slng a[MAXN], c[MAXM];
slng rema[MAXN];
slng sumsel[1<<MAXN];
slng suma, sumc[MAXN];
int n, m;

bool check_feasible(int sel, int seli, int ci, int remc) {
	int lastone = -1, i;

	for (i = n-1; i >= 0; i--) {
		if ((seli & (1 << i)) != 0) {
			lastone = i;
		} else if (lastone != -1 && (sel & (1 << i)) == 0) {
			if ((slng) remc + a[lastone] - a[i] >= 0) {
				VDEBUG("remc=%d lastone=%d i=%d\n", remc, lastone, i);
				return false; /* can substitute with bigger. */
			}
			lastone = -1;
		}
	}
	return true;
}

int fullmask;
int ubound;
slng cnt;
bool find(int sel, int seli, int ai, int amax, int ci, int remc) {
	int i;
	cnt++;
	if (cnt % 100000000 == 0) {
		DEBUG(".");
	}
	VDEBUG("sel = %x seli = %x ci = %d\n", sel, seli, ci);
	if (ci == ubound) {
		return sumsel[sel ^ fullmask] <= remc;
	} else if (a[amax-1] > remc) {
		/* no more can fit. */
		if (!check_feasible(sel, seli, ci, remc))
			return false;
		return find(sel, 0, 0, amax, ci+1, c[ci+1]);
	} else if (sumsel[fullmask ^ sel] > sumc[ubound] - sumc[ci] + remc) {
		/* all remaining don't fit in remaining capacity. */
		return false;
	}

	for (i = ai; i < amax; i++) {
		if (sel & (1 << i) == 1)
			continue;
		VDEBUG("i = %d a[i] = %lld remc = %d\n", i, a[i], remc); 
		if (a[i] > remc)
			continue;
		
		// All remaining fit, move to next backpack.
		// mask for ai, ai+1, ...
		int m = fullmask - ((1 << i) - 1);
		if (sumsel[(sel & m) ^ m] <= remc) {
			if (!check_feasible(sel | m, seli | m, ci, remc - sumsel[(sel & m) ^ m]))
				return false;
			return find(sel | m, 0, 0, i, ci+1, c[ci+1]);
		}
		
		/* i != amax-1 or we would have exited through "all remaining fit". */
		if (find(sel | (1 << i), seli | (1 << i), i+1, amax, ci, remc - a[i]))
			return true;
	}
	return false;
}

int main() {
	int i, j;
	int lbound = 0;
	
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%lld", &a[i]);
		suma += a[i];
	}
	for (i = 0; i < m; i++) {
		scanf("%lld", &c[i]);
	}
	sort(a, a + n, slng_inv);
	sort(c, c + m, slng_inv);
	if (m > n)
		m = n;

	for (i = 0; i < (1 << n); i++) {
		int k = i;
		sumsel[i] = 0;
		for (j = 0; j < n; j++) {
			sumsel[i] += (k & 1) * a[j];
			k = (k >> 1);
		}
	}
	fullmask = (1 << n) - 1;
	
	sumc[0] = c[0];
	if (sumc[0] >= suma) {
		printf("1\n");
		return 0;
	}
	for (i = 1; i < m; i++) {
		sumc[i] = sumc[i-1] + c[i];
	}
	if (sumc[m - 1] < suma) {
		printf("NIE\n");
		return 0;
	}
	/* lower bound */
	while (sumc[lbound] < suma)
		lbound++;
	
	for (ubound = lbound; ubound < m; ubound++) {
		DEBUG("ubound = %d\n", ubound);
		if (find(0, 0, 0, n, 0, c[0]))
			break;
		DEBUG("cnt = %lld\n", cnt);
	}
	
	if (ubound < m) {
		printf("%d\n", ubound + 1);
	} else {
		printf("NIE\n");
	}
	DEBUG("cnt = %lld\n", cnt);
	
	return 0;
}