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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <algorithm>
#include <cassert>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)

const unsigned INFU = -1u;
typedef long long LL;
template<class T> inline int size(const T&c) { return c.size(); }

vector<int> W,C;

void ReadInput() {
  int n,m; cin >> n >> m;
  W.reserve(n);
  REP(i,n) {
    int x; cin >> x; W.push_back(x);
  }
  C.reserve(m);
  REP(i,m) {
    int x; cin >> x; C.push_back(x);
  }
}

unsigned *TAB;

inline unsigned Encode(int knapsack, int filled) {
  return (static_cast<unsigned>(knapsack) << 27) | static_cast<unsigned>(filled);
}

inline void Decode(unsigned v, int &knapsack, int &filled) {
  knapsack = v >> 27;
  filled = v & ((1u<<27)-1u);
}

int SolveExponential() {
  int n = size(W);
  {
    void *ptr;
    int ret = posix_memalign(&ptr, 128, (1<<n)*sizeof(unsigned));
    assert(ret==0);
    TAB = reinterpret_cast<unsigned*>(ptr);
  }
  TAB = new unsigned[1<<n];
  REP(i,1<<n) TAB[i] = INFU;
  TAB[0] = Encode(0,0);
  for(unsigned s=0;s<(1u<<n);++s) {
    unsigned v = TAB[s];
    if(v==INFU) continue;
    int knapsack, filled; Decode(v, knapsack, filled);
    REP(i,n) {
      unsigned s2 = s | (1u<<i);
      if(s2 == s) continue;
      int filled2 = filled + W[i];
      unsigned v2;
      if(filled2 <= C[knapsack]) v2 = Encode(knapsack, filled2);
      else if(W[i] <= C[knapsack+1]) v2 = Encode(knapsack+1, W[i]);
      else continue;
      unsigned &tt = TAB[s2];
      tt = min(tt, v2);
    }
  }
  unsigned res = TAB[(1u<<n)-1u];
  if(res==INFU) return -1;
  int resKnapsack, resFilled;
  Decode(res, resKnapsack, resFilled);
  return resKnapsack+1;
}

bool CanAchieveSum(int alpha, int beta) {
  int n = size(W);
  int n1 = n/2;
  int n2 = n-n1;
  vector<int> left; left.reserve(1<<n1);
  vector<int> right; right.reserve(1<<n2);
  for(unsigned s=0;s<(1u<<n1);++s) {
    int sum = 0;
    REP(i,n1) if(s&(1u<<i)) sum += W[i];
    left.push_back(sum);
  }
  for(unsigned s=0;s<(1u<<n2);++s) {
    int sum = 0;
    REP(i,n2) if(s&(1u<<i)) sum += W[n1+i];
    right.push_back(sum);
  }
  sort(left.begin(), left.end());
  sort(right.begin(), right.end());
  auto p = right.end(); --p;
  for(int s1 : left) {
    while(s1 + *p > beta) {
      if(p==right.begin()) return false;
      --p;
    }
    if(s1 + *p >= alpha) return true;
  }
  return false;
}

int Solve() {
  sort(C.begin(), C.end(), greater<int>());
  if(size(C) > size(W)) C.resize(size(W));
  C.push_back(0);

  LL sumW = 0; for(int w : W) sumW += w;
  LL sumC = 0; for(int c : C) sumC += c;
  if(sumW > sumC) return -1;
  if(sumW <= C[0]) return 1;
  if(sumW <= C[0]+C[1] && CanAchieveSum(static_cast<int>(sumW)-C[0], C[1])) return 2;

  return SolveExponential();
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  ReadInput();
  int res = Solve();
  if(res==-1) cout << "NIE\n";
  else cout << res << '\n';
}