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

typedef unsigned long UL;
typedef unsigned long long ULL;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;

ii drags[100000];

#define FOR(i,a,b) for(int i=a;i<b;i++)
#define MAX_POINTS	2000
#define TR(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)

bool down (int i, int j) { 
  return (drags[i].second == drags[j].second) ? (drags[i].first < drags[j].first) : (drags[i].second > drags[j].second);
}
bool up (int i, int j) { 
  return (drags[i].first == drags[j].first) ? (drags[i].second > drags[j].second) : (drags[i].first < drags[j].first);
}

int main()
{
  int n,e;
  vi pos;
  vi neg;
  ii p;
  
  scanf("%d", &n);
  scanf("%d", &e);

  FOR(i,0,n) {
    scanf("%d", &(drags[i].first));
    scanf("%d", &(drags[i].second));
    if (drags[i].first <= drags[i].second){
      pos.push_back(i);
    }
    else
      neg.push_back(i);
  }

  std::sort (neg.begin(), neg.end(), down); 
  std::sort (pos.begin(), pos.end(), up); 

  bool possible = true;
  TR (ptr, pos)
  {
    e -= drags[*ptr].first;
    if (e <= 0) { possible = false; break; }
    e += drags[*ptr].second;
  }
  TR (ptr, neg)
  {
    e -= drags[*ptr].first;
    if (e <= 0) { possible = false; break; }
    e += drags[*ptr].second;
  }

  if (!possible){
    printf("NIE\n");
    return 0;
  }
  printf("TAK\n");

  TR (ptr, pos) printf("%d ", (*ptr) + 1);
  TR (ptr, neg) printf("%d ", (*ptr) + 1);
  printf("\n");


  return 0;
}