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
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#include <random>

#define REP(i,n) for(int i=0; i<(n); ++i)
#define FORD(i,p,k) for(int i=(p); i>=(k); --i)

struct Mon { int i,d,a; };

std::mt19937 rnd(728934792);

struct In
{
  int z;
  std::vector<Mon> M;

  void read()
  {
    int n; scanf("%d%d",&n,&z);
    M.resize(n);
    REP(i,n){ M[i].i = i; scanf("%d%d",&M[i].d,&M[i].a); }
  }

  void gen()
  {
    unsigned int n = 10, x = 10;
    z = rnd()%x;
    M.resize(rnd()%n);
    REP(i,M.size()) M[i] = Mon{i,int(rnd()%x),int(rnd()%x)};
  }

  void print() const
  {
    printf("n=%d; z=%d\n",M.size(),z);
    for(auto &m : M) printf("%d %d\n",m.d,m.a);
  }

  bool valid(const std::vector<int> &M2) const
  {
    assert(M.size()==M2.size());
    int c = z;
    REP(i,M.size())
    {
      c -= M[M2[i]].d;
      if(c<=0) return 0;
      c += M[M2[i]].a;
    }
    return 1;
  }
};

bool less_d(const Mon &a, const Mon &b){ return a.d<b.d; }
bool less_a(const Mon &a, const Mon &b){ return a.a<b.a; }

bool go(const In &I, std::vector<int> &res)
{
  std::vector<Mon> P,N;
  for(auto &m : I.M) (m.d<m.a?P:N).push_back(m);
  std::sort(P.begin(),P.end(),less_d);
  std::sort(N.begin(),N.end(),less_a);
  res.clear();
  REP(i,P.size()) res.push_back(P[i].i);
  FORD(i,N.size()-1,0) res.push_back(N[i].i);
  return I.valid(res);
}

bool brute(const In &I, std::vector<int> &res)
{
  res.resize(I.M.size()); REP(i,res.size()) res[i] = i;
  while(1)
  {
    if(I.valid(res)) return 1;
    if(!std::next_permutation(res.begin(),res.end())) break;
  }
  return 0;
}

void test()
{
  std::vector<int> res;
  for(int c=0;;c++)
  {
    In I; I.gen();
    bool s = go(I,res); if(s) assert(I.valid(res));
    bool b = brute(I,res); if(b) assert(I.valid(res));
    if(s^b)
    {
      printf("ERROR s=%d; b=%d\n",s,b);
      I.print();
      exit(1);
    }
    if(!(c%100)) printf("ok %d\n",c);
  }
}

int main()
{
  //test();
  In I; I.read();
  std::vector<int> res;
  if(go(I,res))
  {
    puts("TAK");
    for(auto i : res) printf("%d ",i+1);
    puts("");
  } else puts("NIE");

  return 0;
}