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
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <utility>
#include <set>
#include <map>
#include <queue>
using namespace std;

typedef long long LL;

#define FOR(x,b,e) for(int x=b; x<=(e); ++x)
#define REP(x,n) for(int x=0; x<(n); ++x)
#define FORD(x,b,e) for(int x=b; x>=(e); --x)
typedef pair<int,int> PII;
typedef pair<int,pair<int,int> > PIII;
#define MP make_pair 
#define MAXN 1000005
#define ST first
#define ND second
struct STR{
 int ind,c,p;
};
int n;
vector<STR> t;
vector<STR> tr;
void pr(const PIII& p){
  printf("%d %d %d\n",p.ST,p.ND.ST,p.ND.ND);
}

struct cmp
{
  inline bool operator() (const STR& p1, const STR& p2){
    //pr(p1); pr(p2);
    if(p1.p == p2.p && p1.c==p2.c)
      return p1.ind<p2.ind;
    if(p1.c==p2.c)
      return p1.ind<p2.ind;
    return p1.c < p2.c;
  }
};

int main() {
  LL z;

  scanf("%d%lld",&n,&z);
  int a,b;
  REP(x,n){
    STR *str = new STR();
    scanf("%d%d",&(str->c),&(str->p)); str->ind=x+1;
    if(str->c <= str->p){
      t.push_back(*str);
    }else{
      swap(str->c, str->p);
      tr.push_back(*str);
    }
  }

  sort(t.begin(),t.end(),cmp());
  sort(tr.begin(),tr.end(),cmp());
  //REP(x,t.size()){printf("%d %d %d\n",t[x].ind,t[x].c,t[x].p);}
  REP(x,t.size()){
    //printf("%lld %d\n",z,t[x].c);
    z -= t[x].c;
    if(z<=0){
      printf("NIE\n");
      return 0;

    }
    z += t[x].p;
  }
  //printf("after z %lld\n",z);
  LL sum=0;
  REP(x,tr.size())sum+=tr[x].p-tr[x].c;
  LL z2 = z - sum;
  
  REP(x,tr.size()){
    z2 -= tr[x].c;
    if(z2<=0){
      printf("NIE\n");
      return 0;
    }
    z2+=tr[x].p;
  }  

  printf("TAK\n");
  REP(x,t.size()){
      printf("%d ",t[x].ind);
  }
  FORD(x,tr.size()-1,0)printf("%d ",tr[x].ind);
  printf("\n");
  return 0;
}