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

using namespace std;

#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))


struct monster {
  long long int d,a;
  int id;
};

int n,i,j,m1,m2,nr;
long long int z,di,ai;
vector<monster> mon1(100000),mon2(100000), mon3(100000);
vector<int> r(100000);

bool sf1(monster i, monster j) {
  return (i.d<j.d || (i.d==j.d && (i.a-i.d)>(j.a-j.d)));
}

bool sf2(monster i, monster j) {
  return ((i.a-i.d)>(j.a-j.d));
}

bool sf3(monster i, monster j) {
  return (i.d>j.d || (i.d==j.d && (i.a-i.d)>(j.a-j.d)));
}

int main() {
  
scanf("%d %Ld\n",&n,&z);

for(i=0,m1=0,m2=0;i<n;i++) {
  scanf("%Ld %Ld\n",&di,&ai);
  if(ai-di<0) {
    mon2[m2].d=di;
    mon2[m2].a=ai;
    mon2[m2].id=i+1;
    mon3[m2].d=di;
    mon3[m2].a=ai;
    mon3[m2].id=i+1;
    m2++;
  } else {
    mon1[m1].d=di;
    mon1[m1].a=ai;
    mon1[m1].id=i+1;
    m1++;
  }
}

sort(mon1.begin(),mon1.begin()+(m1),sf1);
sort(mon2.begin(),mon2.begin()+(m2),sf2);
sort(mon3.begin(),mon3.begin()+(m2),sf3);


for(i=0,nr=0;i<m1;i++) {
  if(z-mon1[i].d>0) {
    z=z-mon1[i].d+mon1[i].a;
    r[nr]=mon1[i].id;
    nr++;
//    printf("h0\n");
  } else {
    printf("NIE\n");
    return 0;
  }
}

vector<int> v2(m1+m2);
fill(v2.begin(),v2.begin()+(m1+m2),1);
for(i=0,j=0;nr<m2+m1;nr++) {
//  printf("nr=%d, v2=%d,%d,%d\n",nr,v2[0],v2[1],v2[2]);
  if(z-mon2[i].d>0 && 
     (nr==m1+m2-1 || mon2[i].id!=mon3[j].id && z-mon2[i].d+mon2[i].a>mon3[j].d)) {
//    printf("h1 i=%d, j=%d\n",i,j);
    z=z-mon2[i].d+mon2[i].a;
    r[nr]=mon2[i].id;
    v2[mon2[i].id-1]=0;
    i++;
  } else if(z-mon2[i].d>0 && (mon2[i].id!=mon3[j].id && z-mon3[j].d>0)) {
//    printf("h2 i=%d, j=%d\n",i,j);
    z=z-mon3[j].d+mon3[j].a;
    r[nr]=mon3[j].id;
    v2[mon3[j].id-1]=0;
    j++;
  } else if(z-mon2[i].d>0 && mon2[i].id==mon3[j].id) {
//    printf("h3 i=%d, j=%d\n",i,j);
    z=z-mon2[i].d+mon2[i].a;
    r[nr]=mon2[i].id;
    v2[mon2[i].id-1]=0;
    i++;
    v2[mon3[j].id-1]=0;
    j++;
  } else {
//    printf("h4 i=%d, j=%d\n",i,j);
//    printf("mon2=%d,%d,  mon3=%d,%d\n",mon2[0].id,mon2[1].id,mon3[0].id,mon3[1].id);
    printf("NIE\n");
    return 0;
  }
  while(i<m2 && v2[mon2[i].id-1]==0) i++;
  while(j<m2 && v2[mon3[j].id-1]==0) j++;
}

printf("TAK\n");
for(i=0;i<n;i++) {
  printf("%d ",r[i]);
}
printf("\n");

return 0;
}