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
#include<iostream>
#include<vector>
#include<algorithm>

#define VECUINT std::vector<unsigned int>
#define PUII std::pair<unsigned int, unsigned int>
#define VECPUII std::vector<PUII >

const unsigned int INF=1000000009;

unsigned int getMin(const VECUINT & produkty, const VECUINT & plecaki){
	VECUINT P(produkty.size());
	P[0]=1;
	for(unsigned int i=1;i<P.size();++i) P[i]=(P[i-1]<<1);
	unsigned int m=(P[P.size()-1]<<1);
	VECPUII rozwiazanie(m,PUII(INF,INF));
	rozwiazanie[0]=PUII(1,0);
	for(unsigned int i=1;i<m;++i){
		for(unsigned int l=i,j=0;l>0;l>>=1,++j)
			if(l%2==1)
			{
				PUII c=rozwiazanie[i-P[j]];
				if((produkty[j]+c.second)<=plecaki[c.first-1]){
					PUII q=PUII(c.first,c.second+produkty[j]);
					if(q.first==rozwiazanie[i].first&&q.second<rozwiazanie[i].second)
						rozwiazanie[i]=q;
					else if(q.first<rozwiazanie[i].first)
						rozwiazanie[i]=q;
				}
				else if(c.first<plecaki.size()&&produkty[j]<=plecaki[c.first]){
					PUII q=PUII(c.first+1,produkty[j]);
					if(q.first==rozwiazanie[i].first&&q.second<rozwiazanie[i].second)
						rozwiazanie[i]=q;
					else if(q.first<rozwiazanie[i].first)
						rozwiazanie[i]=q;
				}
			}
			
		if(rozwiazanie[i].first>=INF) return INF;
	}
	
	return rozwiazanie[m-1].first;
}

int main(){
	std::ios_base::sync_with_stdio(false);
	
	unsigned int n,m;
	std::cin>>n>>m;
	
	VECUINT produkty(n),plecaki(m);
	for(unsigned int i=0;i<n;++i)
		std::cin>>produkty[i];
	for(unsigned int i=0;i<m;++i)
		std::cin>>plecaki[i];
	std::sort(plecaki.begin(),plecaki.end(),std::greater<unsigned int>());
	
	unsigned int R=getMin(produkty,plecaki);
	if(R<INF) std::cout<<R<<"\n";
	else std::cout<<"NIE"<<"\n";
	
	return 0;
}