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
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

using namespace std;

const int MAX_N = 24;
const int MAX_M = 110;
int n, m;
int d[MAX_N];
int p[MAX_M];

const int MAX_W = (1<<24) + 5;
int sum[MAX_W];
vector<int> moves;
char w[MAX_W];  // FIXME: pamiec?

int sum_one(int mask, int limit) {
    int res = 0;
    REP(i, n) {
        if (mask & (1<<i)) {
            res += d[i];
            if (res > limit) break;
        }
    }
    return res;
}

void licz_sum() {
    FOR(i, 1, (1<<n)) {
        sum[i] = sum_one(i, p[0]);
    }
}

void licz_inne_moves(int bin) {
    moves.clear();
    FOR(i, 1, (1<<n)) {
        if (sum[i] <= p[bin]) {
            int first = n-1;
            while (i & (1<<first)) first--;
            if (sum[i] + d[first] <= p[bin]) continue;

            moves.push_back(i);
        }
    }
}

bool dajesz(int bin) {
    licz_inne_moves(bin);

    for (int pos = (1<<n)-1; pos >= 0; pos--) {
        if (w[pos] != bin+1) continue;
        REP(i, moves.size()) {
            int x = moves[i];
            if (!w[pos|x]) {
                w[pos | x] = bin+2;
            }
        }
        if ((pos & (pos+1)) == 0) break;
    }
    return w[(1<<n)-1];
}

int main() {
    scanf("%d %d", &n, &m);
    REP(i, n) scanf("%d", &d[i]);
    REP(i, m) scanf("%d", &p[i]);
    sort(d, d+n, greater<int>());
    sort(p, p+m, greater<int>());
    m = min(m, n);

    long long total = 0;
    REP(i, n) total += d[i];
    if (total <= (long long)(p[0])) {
        printf("1\n");
        return 0;
    }

    licz_sum();

    REP(i, MAX_W) w[i] = 0;
    w[0] = 1;

    REP(i, m) {
//        printf("bin = %d\n", i);
        if (dajesz(i)) {
            printf("%d\n", i+1);
            return 0;
        }
    }

    printf("NIE\n");
    return 0;
}