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
92
93
94
95
96
97
98
99
#include <algorithm>
#include <cassert>
#include <iostream>
using namespace std;

namespace {
  unsigned make(unsigned a, unsigned b)
  {
    return (a << 27) | b;
  }

  unsigned get_first(unsigned p)
  {
    return p >> 27;
  }

  unsigned get_second(unsigned p)
  {
    return p & ((1U << 27) - 1);
  }

  int solve(vector<unsigned> items, vector<unsigned> packs)
  {
    sort(items.begin(), items.end());
    sort(packs.begin(), packs.end(), greater<unsigned>());

    if (packs.size() > items.size()) {
      packs.resize(items.size());
    }
    while (!packs.empty() && packs.back() < items.front()) packs.pop_back();

    if (packs.empty() || items.back() > packs.front()) return -1;

    unsigned const items_total = accumulate(items.begin(), items.end(), 0U);
    unsigned const packs_total = accumulate(packs.begin(), packs.end(), 0U);

    if (items_total > packs_total) return -1;

    unsigned const n = items.size();
    unsigned const m = packs.size();

    unsigned const N = 1 << n;

    vector<unsigned> dist(N, make(m, 0));
    dist[0] = make(0, 0);

    for (unsigned S = 0; S < N; ++S) {
      unsigned Z = (~S) & (N-1);
      while (Z > 0) {
        unsigned T = Z & ~(Z-1);
        Z ^= T;
        unsigned i = __builtin_ctz(T);
        unsigned const x = items[i];
        unsigned q = get_first(dist[S]);
        unsigned w = get_second(dist[S]);
        if (q >= m) continue;
        w += x;
        if (w > packs[q]) {
          ++q;
          w = x;
          if (q >= m || w > packs[q]) continue;
        }
        unsigned U = S | T;
        auto p = make(q, w);
        if (dist[U] > p) dist[U] = p;
      }
    }

    auto res = get_first(dist.back());
    if (res < m) return res + 1;
    return -1;
  }
}

int main()
{
  iostream::sync_with_stdio(false);
  cin.tie(NULL);

  unsigned n, m;
  cin >> n >> m;

  vector<unsigned> items(n);
  for (unsigned i = 0; i < n; ++i) {
    cin >> items[i];
  }

  vector<unsigned> packs(m);
  for (unsigned i = 0; i < m; ++i) {
    cin >> packs[i];
  }

  int res = solve(move(items), move(packs));

  if (res < 0) cout << "NIE\n";
  else cout << res << '\n';

  return 0;
}