Pakowanie

#include <vector>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>

#define FOR(i,a,b)  for(int i=(a);i<(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define REP(i,a)    FOR(i,0,a)
#define MP          make_pair
#define PB          push_back
#define ST          first
#define ND          second

using namespace std;

typedef vector<int>             VI;
typedef vector<VI>              VVI;
typedef pair<int, int>          PII;
typedef vector<PII>             VII;
typedef long long int           LL;
typedef unsigned long long int  ULL;


const int MAXN = 26;
const int MAXM = 105;
const int INF = 1000000000;

int n, m;

VI objects;
VI bags;
LL bags_sums[MAXM];

LL obj_sum, bags_sum;
LL waste[MAXN];
LL maxWaste;
int minBagIdx;

PII all_set[(1<<24) + 5];
int all_set_size;
VII sets[MAXN];
int max_set_idx[MAXN];

void init_sets() {
    all_set_size = 0;
    FOR (i, 0, n) {
        int tmp_num = all_set_size;
        REP (j, tmp_num) {
            if (objects[i] + all_set[j].ST <= bags.back()) {
                all_set[all_set_size] = {objects[i] + all_set[j].ST, all_set[j].ND | (1 << i)};
                ++all_set_size;
            }
        }
        all_set[all_set_size] = {objects[i], 1 << i};
        ++all_set_size;
    }
    sort(all_set, all_set + all_set_size);

    int idx = all_set_size-1;
    FORD (i, m-1, 0) {
        while (idx > 0 && all_set[idx].ST > bags[i]) {
            --idx;
        }
        max_set_idx[i] = idx;
    }
}

void init_set(int bagIdx) {
    FORD (i, max_set_idx[bagIdx], 0) {
        bool add = true;
        auto elem = all_set[i];
        for (auto x : sets[bagIdx]) {
            if ((elem.ND & x.ND) == elem.ND) {
                add = false;
                break;
            }
        }

        if (add) {
            sets[bagIdx].PB(elem);
        }
    }
}

int lower[1<<12], higher[1<<12];
const int LOW_MASK = (1<<12) - 1;

inline int weight(int mask) {
    return lower[mask & LOW_MASK] + higher[(mask >> 12) & LOW_MASK];
}

void init_weights() {
    REP (i, min(12, n)) {
        REP (j, 1<<12) {
            if (j & (1<<i)) {
                lower[j] = min(INF, lower[j] + objects[i]);
            }
        }
    }
    REP (i, min(12, n-12)) {
        REP (j, 1<<12) {
            if (j & (1<<i)) {
               higher[j] = min(INF, higher[j] + objects[i+12]);
            }
        }
    }
}


PII dfs_tmp[MAXN][1<<16], dfs_filtered[MAXN][1<<16];
int dfs_filtered_size[MAXN];
bool dfs_add;

inline bool cmp(PII a, PII b) {
    if (__builtin_popcount(a.ND) == __builtin_popcount(b.ND)) {
        return a.ST > b.ST;
    }
    else {
        return (__builtin_popcount(a.ND) < __builtin_popcount(b.ND));
    }
}

const int THROW_DEPTH = 7;
const int CALL_LIMIT = 1500000;
int calls;

bool no_exception;

void DFS(int bagIdx, int notPacked) {
    ++calls;
    if (no_exception && bagIdx - minBagIdx == THROW_DEPTH) {
        if (calls > CALL_LIMIT) {
            throw 1;
        }
    }

    REP (i, int(sets[bagIdx].size())) {
        dfs_tmp[bagIdx][i] = {weight(sets[bagIdx][i].ND & notPacked), sets[bagIdx][i].ND & notPacked};
    }
    sort(dfs_tmp[bagIdx], dfs_tmp[bagIdx] + sets[bagIdx].size());

    dfs_filtered_size[bagIdx] = 0;
    FORD (i, sets[bagIdx].size()-1, 0) {
        dfs_add = true;
        auto new_x = dfs_tmp[bagIdx][i];
        REP (j, dfs_filtered_size[bagIdx]) {
            auto old_x = dfs_filtered[bagIdx][j];
            if ((new_x.ND & old_x.ND) == new_x.ND
                    || ((__builtin_popcount(old_x.ND) == __builtin_popcount(new_x.ND)) && (__builtin_popcount(new_x.ND ^ old_x.ND) == 2))) {
                dfs_add = false;
                break;
            }
        }
        if (dfs_add) {
            dfs_filtered[bagIdx][dfs_filtered_size[bagIdx]] = dfs_tmp[bagIdx][i];
            ++dfs_filtered_size[bagIdx];
        }
    }

    sort(dfs_filtered[bagIdx], dfs_filtered[bagIdx]+dfs_filtered_size[bagIdx], cmp);

    REP (i, dfs_filtered_size[bagIdx]) {
        auto x = dfs_filtered[bagIdx][i];
        if (waste[bagIdx] + bags[bagIdx] - x.ST > maxWaste) {
            continue;
        }

        if (bagIdx == m - 1) {
            if ((notPacked ^ x.ND) == 0) {
                printf("%d\n", m-minBagIdx);
                exit(0);
            }
        }
        else {
            waste[bagIdx + 1] = waste[bagIdx] + bags[bagIdx] - x.ST;
            DFS(bagIdx + 1, notPacked ^ x.ND);
        }
    }
}


int main() {
    scanf("%d %d", &n, &m);

    int tmp;
    int max_obj = 0;
    REP (i, n) {
        scanf("%d", &tmp);
        objects.PB(tmp);
        obj_sum += objects[i];
        max_obj = max(max_obj, objects[i]);
    }
    sort(objects.begin(), objects.end());

    int max_bag = 0;
    REP (i, m) {
        scanf("%d", &tmp);
        // if some object can fit in bag
        if (tmp >= objects[0]) {
            bags.PB(tmp);
            bags_sum += bags.back();
            max_bag = max(max_bag, bags.back());
        }
    }
    m = bags.size();
    sort(bags.begin(), bags.end());

    // no solution
    if (m == 0 || obj_sum > bags_sum || max_obj > max_bag) {
        printf("NIE\n");
        return 0;
    }

    // too many bags
    if (m > n) {
        VI tmpVec = bags;
        bags.clear();
        FOR (i, m-n, m) {
            bags.PB(tmpVec[i]);
        }
        m = bags.size();
    }

    // init bag_sums
    bags_sums[m-1] = bags[m-1];
    FORD (i, m-1, 1) {
        bags_sums[i-1] = bags_sums[i] + bags[i-1];
    }

    init_sets();
    init_weights();

    no_exception = true;
    FORD (i, m-1, 0) {
        init_set(i);
        waste[i] = 0;
        maxWaste = bags_sums[i] - obj_sum;
        if (maxWaste < 0) {
            continue;
        }
        minBagIdx = i;
        try {
            calls = 0;
            DFS(minBagIdx, (1 << n) - 1);
        }
        catch (...) {
            no_exception = false;
        }
    }

    printf("NIE\n");

    return 0;
}