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
#include<stdio.h>
#include<stdlib.h>

struct potwor {
    int numer;
    int obrazenia;
    int eliksir;
};

int porownaj(const void * a, const void * b) {

	struct potwor _a=*(struct potwor*)a;
	struct potwor _b=*(struct potwor*)b;

	return _a.obrazenia-_b.obrazenia;
	
}

int porownaj2(const void * a, const void * b) {

	struct potwor _a=*(struct potwor*)a;
	struct potwor _b=*(struct potwor*)b;

	if( _b.obrazenia-_a.obrazenia )
		return _b.obrazenia-_a.obrazenia;
	else
		return _b.eliksir-_a.eliksir;
	
}

main(){
    int liczba_potworow,obrazenia,eliksir,i=0,j=0,k=0,l=0;
    long long int zdrowie;
    struct potwor premia[100000];
    struct potwor deficyt[100000];

    scanf("%d %lli",&liczba_potworow,&zdrowie);
    for(i=0;i<liczba_potworow;i++) {
	scanf("%d %d",&obrazenia,&eliksir);
	if(obrazenia>eliksir) {
	    deficyt[j].numer=i+1;
	    deficyt[j].obrazenia=obrazenia;
	    deficyt[j].eliksir=eliksir;
	    j++;
	} else {
	    premia[k].numer=i+1;
	    premia[k].obrazenia=obrazenia;
	    premia[k].eliksir=eliksir;
	    k++;
	}
    }

    qsort(premia,k,sizeof(struct potwor),porownaj);

/*    for(i=0;i<k;i++) {
	printf("%d %d %d\n",premia[i].numer,premia[i].obrazenia,premia[i].eliksir);
    }*/

    qsort(deficyt,j,sizeof(struct potwor),porownaj2);

     /*for(i=0;i<j;i++) {
	printf("%d %d %d\n",deficyt[i].numer,deficyt[i].obrazenia,deficyt[i].eliksir);
    }*/

    for(i=0;i<k;i++) {
    	if(premia[i].obrazenia<zdrowie) {
	    zdrowie=zdrowie-premia[i].obrazenia+premia[i].eliksir;
	} else {
	    printf("NIE\n");
	    return 0;
	}
    }

    for(i=0;i<j;i++) {
    	if(deficyt[i].obrazenia<zdrowie) {
	    zdrowie=zdrowie-deficyt[i].obrazenia+deficyt[i].eliksir;
	} else {
	    printf("NIE\n");
	    return 0;
	}
    }
    printf("TAK\n");
    for(i=0;i<k;i++) {
	printf("%d ",premia[i].numer);
    }
    for(i=0;i<j;i++) {
	printf("%d ",deficyt[i].numer);
    }
    printf("\n");
    return 0;
     
}