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

using namespace std;

int ile[1<<24], luzOst[1<<24];

int main()
{
  ios_base::sync_with_stdio(false);
  int n, m, a[24], p[100];
  cin>>n>>m;
  for (int i=0; i<n; ++i)
    cin>>a[i];
  for (int i=0; i<m; ++i)
    cin>>p[i];
  sort(p, p+m);
  reverse(p, p+m);
  for (int i=1, k=1<<n; i<k; ++i)
    ile[i]=100;
  for (int i=0, k=1<<n; i<k; ++i)
  {
    if (ile[i]==100)
      break;
    for (int j=0; j<n; ++j)
    {
      int bit=1<<j;
      if (i&bit)
        continue;
      int il, lu;
      if (a[j]<=luzOst[i])
      {
        il=ile[i];
        lu=luzOst[i]-a[j];
      }
      else
      {
        il=ile[i]+1;
        if (il>m)
          continue;
        lu=p[il-1]-a[j];
        if (lu<0)
          continue;
      }
      int suma=i|bit;
      if (il<ile[suma] || (il==ile[suma] && lu>luzOst[suma]))
      {
        ile[suma]=il;
        luzOst[suma]=lu;
      }
    }
  }
  if (ile[(1<<n)-1]==100) cout<<"NIE"<<endl;
  else cout<<ile[(1<<n)-1]<<endl;
  return 0;
}