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
#include<iostream>
#include<algorithm>
using namespace std;
int pot[30];
int a[24],b[100],c[24];
bool ok(int M,int nr){
	int suma=0;
	for(int i=0;i<24;i++)if(M&pot[i])suma+=a[i];
	return suma<=c[nr];	
}
bool caly[16777216];
int dasie[16777216],caly2[16777216];
main(){
pot[0]=1;
for(int i=1;i<30;i++)pot[i]=pot[i-1]*2;
int n,m;
cin>>n>>m;
int duzo=pot[n];
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<m;i++)cin>>b[i];
sort(a,a+n);
sort(b,b+m);
for(int i=0;i<n;i++)c[i]=b[m-n+i];
if(a[n-1]>c[n-1]){cout<<"NIE\n";return 0;}
for(int i=0;i<duzo;i++)caly[i]=ok(i,n-1);
//for(int i=0;i<duzo;i++)cout<<i<<" "<<caly[i]<<"\n";
//for(int i=0;i<n;i++)cout<<c[i]<<" ";
//cout<<"\n";
if(caly[duzo-1]){cout<<1<<"\n";return 0;}
int dasiesize,caly2size;
for(int i=n-2;i>=0;i--){
	dasiesize=0;
	caly2size=0;
	for(int j=0;j<duzo;j++)if(ok(j,i)){dasie[dasiesize]=j;dasiesize++;}
	for(int j=0;j<dasiesize;j++)if(caly[(duzo-1)^dasie[j]]){cout<<n-i<<"\n";return 0;}
	for(int j=0;j<duzo;j++)if(caly[j]){caly2[caly2size]=j;caly2size++;}
	//cout<<dasiesize<<" "<<caly2size<<"\n";
	for(int j=0;j<dasiesize;j++){
		for(int k=0;k<caly2size;k++)caly[dasie[j]|caly2[k]]=1;	
	}
}
cout<<"NIE\n";
}