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
#include <cstdlib>
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;


bool is_packable(vector<int> const &A, vector<int> const &C) {
  
  // printf("A: "); for(unsigned int i = 0; i < A.size(); ++i) printf("%d ", A[i]); printf("\n");
  // printf("C: "); for(unsigned int i = 0; i < C.size(); ++i) printf("%d ", C[i]); printf("\n");
  
  if(A.size() == 0) return true;
  
  int64_t aSum = 0;
  for(unsigned int i = 0; i < A.size(); ++i) aSum += A[i];
  
  int64_t cSum = 0;
  for(unsigned int i = 0; i < C.size(); ++i) cSum += C[i];
  
  if(aSum > cSum) return false;
  if(C.size() == 1) return true;
  
  unsigned int h = C.size() >> 1;
  vector<int> C0(h);
  vector<int> C1(C.size() - h);
  for(unsigned int i = 0; i < h; ++i)        C0[i]   = C[i];
  for(unsigned int i = h; i < C.size(); ++i) C1[i-h] = C[i];
  
  int sLimit = 1 << A.size();
  
  for(int s = 0; s < sLimit; ++s) {
    vector<int> A0;
    vector<int> A1;
    
    for(unsigned int i = 0; i < A.size(); ++i) {
      if(s & (1 << i)) {
        A1.push_back(A[i]);
      } else {
        A0.push_back(A[i]);
      }
    }
    
    if(is_packable(A0, C0) and is_packable(A1, C1)) return true;
  }
  
  return false;
}


bool k_good(vector<int> const &A, vector<int> const &C, int const &k) {
  vector<int> CC(k);
  for(int i = 0; i < k; ++i) CC[i] = C[i];
  return is_packable(A, CC);
}

int solve(vector<int> const &A, vector<int> const &C, int const &maxK) {
  int k0 = 1;
  int k1 = maxK;
  if(k_good(A, C, k0)) return 1;
  if(not k_good(A, C, k1)) return -1;
  while(k1 - k0 > 1) {
    int kh = (k0 + k1) >> 1;
    if(k_good(A, C, kh)) {
      k1 = kh;
    } else {
      k0 = kh;
    }
  }
  return k1;
}


int main(int const /*argc*/, char const * const * const /*argv*/) {
  int n, m;
  vector<int> A;
  vector<int> C;
  
  scanf("%d %d", &n, &m);
  
  A.resize(n);
  for(int i = 0; i < n; ++i) scanf("%d", &(A[i]));
  C.resize(m);
  for(int i = 0; i < m; ++i) scanf("%d", &(C[i]));
  
  sort(C.begin(), C.end());
  reverse(C.begin(), C.end());
  
  int k = solve(A, C, min(n, m));
  
  if(k == -1) {
    printf("NIE\n");
  } else {
    printf("%d\n", k);
  }
  
  return EXIT_SUCCESS;
}