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<cstring>

enum {
	MAX = (1<<24) + 4
};

int items[30];
int backpacks[110];

struct state
{
	unsigned short b : 5;
	unsigned int sp : 27;
} states[MAX];

char txt[30];

int convert()
{
	int val = 1;
	int res = 0;
	for(int i = 0; i < sizeof(txt); i++)
	{
		if(txt[i] == 1)
			res += val;
		val <<= 1;
	}
	return res;
}

bool comp(int a, int b)
{
	return a>b;
}

int main()
{
	memset(states,-1,sizeof(states));
	int n, m; scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++)
		scanf("%d",items+i);
	for(int i = 0; i < m; i++)
		scanf("%d",backpacks+i);
	
	std::sort(items,items+n,comp);
	std::sort(backpacks,backpacks+m,comp);
	
	states[0].sp = backpacks[0];
	states[0].b = 0;
	for(int i = 0; i <= n; i++)
	{
		for(int j = 0; j < n; j++)
			txt[j] = (i>j)?1:0;
		do
		{
			int id = convert();
			unsigned short _b = states[id].b;
			unsigned int _sp = states[id].sp;
			for(int k = 0; k < n; k++)
			{
				if(id & (1<<k)) continue;
				unsigned short b = _b;
				unsigned int sp = _sp;
				if(items[k] <= sp)
					sp -= items[k];
				else
					if(items[k] <= backpacks[b+1])
					{
						b++;
						sp = backpacks[b]-items[k];
					}
					else
						break;
				int new_id = id | (1<<k);
				if(states[new_id].b > b ||
					(states[new_id].b == b && states[new_id].sp < sp))
					{
						states[new_id].b = b;
						states[new_id].sp = sp;
					}
			}
		} while(std::next_permutation(txt,txt+n));
	}
	if(states[convert()].b == 31)
		printf("NIE\n");
	else
		printf("%d\n",states[convert()].b+1);
	return 0;
}