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
// Krzysztof Piesiewicz
// Pakowanie [A] PA 2014
#include <cstdio>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAX_N = 30, MAX_M = 107, MAX_SETS = (1 << 24) + 7, INF = 107, DB = 0;

struct Cmp {
	inline bool operator() ( int a, int b ) { return a > b;	}
} cmp;

int n, m, mask, minRes = INF, a[ MAX_N ], c[ MAX_M ], least[ MAX_N ], sum[ MAX_N ], consid[ MAX_SETS ];

void print() {
	for( int i = 0; i < n; i++ )
		printf( "%d", (mask & (1<<i)) >> i );
}

int gen( int i, int knap ) {
	int res = INF;
	if( i == 0 )
		least[ knap ] = INF;
	if( DB ) {
		print();
		printf( " i %d, knap %d, sum %d, least %d\n", i, knap, sum[ knap ], least[ knap ] );
	}
	if( i == n ) {
		if( least[ knap ] == INF )
			minRes = min( minRes, res = knap + 1 );
		else
			if( sum[ knap ] + a[ least[ knap ] ] > c[ knap ] ) {
				if( !( ( consid[ mask ] & (1<<knap) ) >> knap ) ) {
					if( knap + 1 < minRes )
						res = gen( 0, knap + 1 );
					else
						res = minRes;
					consid[ mask ] += (1<< knap);
				}
			}
	} else {
		if( !(mask & (1<<i)) ) {
			if( sum[ knap ] + a[ i ] <= c[ knap ] ) {
				sum[ knap ] += a[ i ];
				mask += (1<<i);
				res = min( res, gen( i + 1, knap ) );
				sum[ knap ] -= a[ i ];
				mask -= (1<<i);
			}
			if( least[ knap ] == INF )
				least[ knap ] = i;
			res = min( res, gen( i + 1, knap ) );
			if( least[ knap ] == i )
				least[ knap ] = INF;
		} else
			res = min( res, gen( i + 1, knap ) );
	}
	return res;
}

int main() {
	scanf( "%d %d", &n, &m );
	for( int i = 0; i < n; i++ )
		scanf( "%d", &a[ i ] );
	for( int i = 0; i < m; i++ )
		scanf( "%d", &c[ i ] );
	sort( c, c + m, cmp );
	sort( a, a + n, cmp );
	int ok = gen( 0, 0 );
	if( DB ) {
		for( int i = 0; i < n; i++ )
			printf( "%d ", a[ i ] );
		printf( "\n" );
		for( int i = 0; i < m; i++ )
			printf( "%d ", c[ i ] );
		printf( "\n" );
	}
	if( minRes <= n )
		printf( "%d\n", minRes );
	else
		printf( "NIE\n" );
	return 0;
}