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
// Author: Adam Krasuski

#include <cstdio>
#include <algorithm>


using namespace std;

int cmp(int a,int b){
    return a>b;
}

int is_possible(int a_size, int a[], int c_size, int c[]){
    if(a_size==0){return 1;}
    for(int i=0;i<c_size;i++){
        if(*a<=c[i]){
            //change the c[i] so as to accomodate for added a[0]
            c[i]-=*a;
            if(is_possible(a_size-1,a+1,c_size,c)){
                c[i]+=*a;
                return 1;
            }
            //return to initial settings
            c[i]+=*a;
        }
    }
    return 0;
}



int bin_s(int left, int right, int c[], int a_size, int a[]){
    //this function will check if there is such a X between left and right inclusively, such that 1==is_possible(a_size,a,X,c)
    //if there is, it will return X
    //if there is not, it will return right+1
    if(left>right){
        return right+1;
    }
    if(left==right){
        if(is_possible(a_size,a,left,c)){
            return left;
        }
        else{
            return right+1;
        }
    }
    int m=(right+left)/2;
    if(is_possible(a_size,a,m,c)){
        //we overshot
        return bin_s(left,m-1,c,a_size,a);
    }
    else{
        //we undershot
        return bin_s(m+1,right,c,a_size,a);
    }
}

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    int a[n];
    int c[m];
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d",&c[i]);
    }
    sort(a,a+n,cmp);
    sort(c,c+m,cmp);

    int result=bin_s(1,min(n,m),c,n,a);
    if(result<=n){
        printf("%d\n",result);
    }
    else{
        printf("NIE\n");
    }
    //for(int i=24;i>=0;i--){
    //    printf("Result for %d: %d\n",i,is_possible(n,a,i,c));
    //}



}