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
// Artur Kraska, II UWr

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cmath>
#include <list>
#include <set>
#include <map>

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(typeof(coll.begin()) iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(typeof(coll.rbegin()) iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#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 MP                          make_pair
#define PB                          push_back
#define deb(X)                      ;

#define M 1000000007
#define INF 1000000007

using namespace std;

int n, m, res = INF, ile = 0;
int p[107], el[107], tab[107][107];

static inline bool comp_rev(const int &a, const int &b)
{
    return b < a;
}

static inline bool check(const int &poz)
{
    forr(i, ile)
        if(tab[poz][i] > p[i])
            return 0;
    return 1;
}

static inline void go(const int &nr)
{
    deb(cout << " poziom " << nr << ": " << endl);
    if(nr == n)
        res = min(res, ile);
    else if(ile < res)
    {
        forr(j, ile)
            tab[nr][j] = tab[nr-1][j];

        forr(i, ile)
        {
            tab[nr][i] += el[nr];
            deb(cout << "   wklada do " << i << "-tego koszyka: ");

            int last_j = i;
            int wart = tab[nr][last_j];
            for(; last_j>0 && wart > tab[nr][last_j-1]; last_j--)
                tab[nr][last_j] = tab[nr][last_j-1];
            tab[nr][last_j] = wart;

            deb(forr(j, ile)
                cout << " " << tab[nr][j];
            cout << endl);

            if(check(nr))
                go(nr+1);

            FOR(j, last_j, i)
                tab[nr][j] = tab[nr-1][j];
        }

        if(ile < res-1 && ile < m)
        {
            //forr(j, ile)
            //    tab[nr][j] = tab[nr-1][j];
            tab[nr][ile] = el[nr];

            for(int j=ile; j>0 && tab[nr][j] > tab[nr][j-1]; j--)
                swap(tab[nr][j], tab[nr][j-1]);

            deb(cout << "   wklada do " << ile << "-tego koszyka: ");

            deb(forr(j, ile+1)
                cout << " " << tab[nr][j];
            cout << endl);

            ile++;
            if(check(nr))
                go(nr+1);
            ile--;
        }
    }

    deb(cout << "wychodzi z poziomu " << nr << endl);
}

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

    forr(i, n)
        scanf("%d", &el[i]);
    sort(el, el+n, comp_rev);
    forr(i, m)
        scanf("%d", &p[i]);
    sort(p, p+m, comp_rev);

    go(0);

    if(res == INF)
        printf("NIE\n");
    else
        printf("%d\n", res);

	return 0;
}