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

#define st first
#define nd second
#define make(a,b) make_pair(a,b)

bool operator> (pair<int,int> A, pair<int,int> B)
{
	if (A.st > B.st) return 1;
	if (A.st < B.st) return 0;
	if (A.nd > B.st) return 1;
	return 0;
}

pair<int,int> operator+ (pair<int,int> A, pair<int,int> B)
{
	return make( A.st+B.st, B.nd+A.nd );
}

pair<int,int> tab[ (1<<24) +2 ];
bitset < (1<<24) +2 > vis;
int po[ 103 ];
int wag[ 26 ];
bool cmp(int a,int b)
{
	return a > b;
}

int newton[26]={1,26,278,2026,10628,42506,134598,346106,735473,1307506,1961258,2496146,2704158,2496146,1961258,1307506,735473,346106,134598,42506,10628,2026,278,26,3,2};

vector <int> kol[26];
int K[26];

long long int ile;

int main()
{
	int n,m, z;
	scanf("%d%d",&n,&m);
	for (int i=0;i<n;i++) scanf("%d",&wag[i]);
	for (int i=0;i<m;i++) scanf("%d",&po[i]);
	for (int i=0;i<25;i++)
		kol[i].resize( newton[i] );
	sort( po, po+m, cmp );
	for (int i=0;i<(1<<n);i++)
		kol[ __builtin_popcount( i ) ][ K[ __builtin_popcount(i) ]++ ] = i;
	K[0]=1;
	vis[0]=1;
	for (int t=0;t<n;t++)
	{
//		printf("t %d\n",t);
		for (int k=0;k<K[t];k++)
		{
			if ( vis[ kol[t][k] ]==0 ) continue;
//			printf("vis %d\n",kol[t][k]);
			for (int i=0;i<n;i++)
			{
				if ( kol[t][k]&(1<<i) ) continue;
				if ( vis[ kol[t][k]|(1<<i) ]==0 )
				{
					if (tab[kol[t][k]].second + wag[i] <= po[ tab[kol[t][k]].first ])
					{
						vis[ kol[t][k]|(1<<i) ]=1;
						tab[ kol[t][k]|(1<<i) ] = make_pair( tab[ kol[t][k] ].first, tab[ kol[t][k] ].second+wag[i]);
					}
					else if ( wag[i] <= po[ tab[ kol[t][k] ].first +1 ]  )
					{
						vis[ kol[t][k]|(1<<i) ]=1;
						tab[ kol[t][k]|(1<<i) ] = make_pair( tab[ kol[t][k] ].first+1, wag[i] );
					}
				}
				else if ( tab[kol[t][k]].second + wag[i] <= po[ tab[kol[t][k] ].first ] )
				{
					if ( tab[ kol[t][k]|(1<<i) ] > make(tab[ kol[t][k] ].first, tab[ kol[t][k] ].second+wag[i] ) )
						tab[ kol[t][k]|(1<<i) ] = make(tab[ kol[t][k] ].first, tab[ kol[t][k] ].second+wag[i] );
				}
				else if ( wag[i] <= po[ tab[ kol[t][k] ].first+1 ] )
				{
					if ( tab[ kol[t][k]|(1<<i) ] > make( tab[ kol[t][k] ].first+1, wag[i] ) )
						tab[ kol[t][k]|(1<<i) ] = make( tab[ kol[t][k] ].first+1, wag[i] );
				}
			}
		}
	}
	if (vis[(1<<n)-1]) printf("%d\n",tab[ (1<<n)-1 ].first+1);
	else printf("NIE\n");
}