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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class pak {

    private static int naive;

    public static void main(final String[] args) {

        final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            reader.readLine();
            final List<Integer> przedm = new LinkedList<Integer>();
            final List<Integer> plec = new LinkedList<Integer>();
            for (final String p : reader.readLine().trim().split("\\s+")) {
                przedm.add(Integer.parseInt(p));
            }
            for (final String p : reader.readLine().trim().split("\\s+")) {
                plec.add(Integer.parseInt(p));
            }
            Collections.sort(przedm, Collections.reverseOrder());
            Collections.sort(plec, Collections.reverseOrder());


            naive = naive(new LinkedList<Integer>(przedm), new LinkedList<Integer>(plec));
            if(naive == -1){
                System.out.println("NIE");
                System.exit(0);
            }


            final int solution = naive == 1 ? 1 : resolve(przedm, plec, plec.remove(0), 0);
            if (solution != -1) {
                System.out.println(1 + solution);
            } else {
                System.out.println("NIE");
            }

        } catch (IOException e) {
            e.printStackTrace();
        }
        System.exit(0);
    }

    private static int naive(List<Integer> przedm, List<Integer> plec) {
        int plecNo = 0;
        while (!przedm.isEmpty()) {
            if (plec.isEmpty()) {
                return -1;
            }
            Iterator<Integer> pIter = przedm.iterator();
            final int przedmiot = pIter.next();
            pIter.remove();
            int plecak = plec.remove(0);
            plecNo++;
            if (plecak < przedmiot) {
                return -1;
            }
            plecak -= przedmiot;
            while (plecak > 0 && pIter.hasNext()) {
                int next = pIter.next();
                if (next <= plecak) {
                    plecak -= next;
                    pIter.remove();
                } else {
                    break;
                }
            }
        }
        return plecNo;
    }


    private static int resolve(List<Integer> przedm, List<Integer> plec, int currentCapacity, int curRes) {
        if(curRes > naive) return -1;
        if (przedm.isEmpty()) return 0;
        int res = -1;
        for (int i = 0; i < przedm.size(); i++) {
            final int cost = przedm.get(i);
            if(i > 0 && cost == przedm.get(i - 1)) continue;
            if (cost <= currentCapacity) {
                currentCapacity -= cost;
                przedm.remove(i);
                final int subSolution = resolve(przedm, plec, currentCapacity, curRes);
                if (subSolution != -1) {
                    if (res == -1) {
                        res = subSolution;
                    } else {
                        if(subSolution > res) {
                            currentCapacity += cost;
                            przedm.add(i, cost);
                            break;
                        }
                        res = subSolution;// Math.min(res, subSolution);
                    }
                }
                currentCapacity += cost;
                przedm.add(i, cost);
            } else {
                if (!plec.isEmpty()) {
                    final int currentPlec = plec.remove(0);
                    if (currentPlec >= (i == 0 ? cost : przedm.get(0))) {
                        final int subSolution = resolve(przedm, plec, currentPlec, curRes + 1);
                        if (subSolution != -1) {
                            if (res == -1) {
                                res = 1 + subSolution;
                            } else {
                                res = Math.min(res, 1 + subSolution);
                            }
                        }
                    }
                    plec.add(0, currentPlec);
                }
                break;
            }
        }
        return res;
    }
}