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
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
#include <ext/numeric>
using namespace std ;
using namespace __gnu_cxx ;
typedef long long LL ;
typedef pair<int,int> PII ;
typedef vector<int> VI ;
const int INF = 1000*1000*100+10 ;
const LL INFLL = (LL)INF * (LL)INF ;
#define REP(i,n) for(i=0;i<(n);++i)
#define ALL(c) c.begin(),c.end()
#define VAR(v,i) __typeof(i) v=(i)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();++i)
#define CLEAR(t) memset(t,0,sizeof(t))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second

const int MAXN = 24 ;
const int MAXM = 110 ;

int n, m ;
int w[MAXM], c[MAXM] ;
int S[1<<MAXN] ;

void fill(int i, int mask, int sum) {
	if(i==n) S[mask]=sum ;
	else {
		fill(i+1, mask, sum) ;
		fill(i+1, mask|(1<<i), min(INF, sum+w[i])) ;
	}
}

void reduct(int *f) {
	for(int mask=0 ; mask<(1<<n) ; mask++) {
//		assert(f[mask]>=0) ;
		f[mask] = (f[mask]!=0) ;
	}
}

void init(int *f, int i) {
	for(int mask=0 ; mask<(1<<n) ; mask++)
		f[mask] = (S[mask] <= c[i]) ;
}

const int MOD=1<<30 ;

void dzeta(int *f) {
	for(int i=n-1 ; i>=0 ; i--)
		for(int preMask=0 ; preMask<(1<<(n-1)) ; preMask++) {
			int mask = (preMask & ((1<<i)-1)) + (1<<i) + ((preMask & (~((1<<i)-1)))<<1) ;
			f[mask] += f[mask^(1<<i)] ;
			f[mask] = f[mask] & (MOD-1) ;
		}
}
void mobius(int *f) {
	for(int i=n-1 ; i>=0 ; i--)
		for(int preMask=0 ; preMask<(1<<(n-1)) ; preMask++) {
			int mask = (preMask & ((1<<i)-1)) + (1<<i) + ((preMask & (~((1<<i)-1)))<<1) ;
			f[mask] -= f[mask^(1<<i)] ;
			f[mask] = (f[mask]+MOD) & (MOD-1) ;
		}
}

void conv(int *f, int *g) {
	dzeta(f) ;
	dzeta(g) ;
	for(int mask=0 ; mask<(1<<n) ; mask++)
		f[mask] = ((LL)f[mask] * g[mask]) & (MOD-1) ;
	mobius(f) ;
}

int f[1<<MAXN] ;
int g[1<<MAXN] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	int i ;
	cin >> n >> m ;
	REP(i,n) cin >> w[i] ;
	REP(i,m) cin >> c[i] ;
	sort(w, w+n, greater<int>()) ;
	sort(c, c+m, greater<int>()) ;
	m = min(n,m) ;
	while(m>0 && c[m-1] < c[n-1]) m-- ;
	
	if(m==0) {
		cout << "NIE" << endl ;
		return 0 ;
	}
	
	fill(0, 0, 0) ;
	
	init(f, 0) ;
	if(f[(1<<n)-1]) {
		cout << 1 << endl ;
		return 0 ;
	}
	for(i=1 ; i<m ; i++) {
		if(i!=1) reduct(f) ;
		init(g, i) ;
		conv(f, g) ;
		if(f[(1<<n)-1]) {
			cout << i+1 << endl ;
			return 0 ;
		}
		//if(i==1) return 0 ;
	}
	cout << "NIE" << endl ;
}