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

typedef struct el {
   int d;
   int a;
   int i;
} element;


int cmp(const void * a, const void * b)
{
   if( (*(element*)a).d -(*(element*)b).d == 0) {
    return ( (*(element*)a).a - (*(element*)b).a );
   } else {
   return ( (*(element*)a).d - (*(element*)b).d );
   }
}

int cmp2(const void * a, const void * b)
{
   if( (*(element*)b).a -(*(element*)a).a == 0) {
    return ( (*(element*)b).d - (*(element*)a).d );
   } else {
   return ( (*(element*)b).a - (*(element*)a).a );
   }
}

element plus[100000];
element minus[100000];

main() {
int n,z,i,d,a;
int p[2];
int plus_c=0;
int minus_c=0;
int min_a=0;
int min_i=0;
long long int pz;
int tak=1;

scanf("%d %lld",&n,&pz);
for(i=1;i<=n;i++) {
scanf("%d %d",&d,&a);
if(d<=a) {
plus[plus_c].i=i;
plus[plus_c].d=d;
plus[plus_c++].a=a;
} else {
minus[minus_c].i=i;
minus[minus_c].d=d;
minus[minus_c++].a=a;
}
}

qsort(plus,plus_c,sizeof(element),cmp);
qsort(minus,minus_c,sizeof(element),cmp2);

for(i=0;i<plus_c;i++) {
pz-=plus[i].d;
if(pz<=0){tak=0;}
pz+=plus[i].a;
}

for(i=0;i<minus_c;i++) {
pz-=minus[i].d;
if(pz<=0){tak=0;}
pz+=minus[i].a;
}

if(tak) {
printf("TAK\n");
for(i=0;i<plus_c;i++) printf("%d ",plus[i].i);
for(i=0;i<minus_c;i++) printf("%d ",minus[i].i);
} else {
printf("NIE\n");
}

return 0;
}