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
#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

struct Monster {
  Monster(int i, int dd, int aa) : idx(i), d(dd), a(aa), diff(a-d) {}
  int idx;
  int d;
  int a;
  int diff;
  bool operator<(const Monster & o) const {
    if (diff * o.diff < 0) return diff > o.diff; // positive diff first
    if (diff * o.diff == 0) {
      if (diff != o.diff) return diff > o.diff; // 0 before negative
      return d < o.d; // less cost first
    }
    // same diff sign
    if (diff > 0) return d < o.d;
    else return d > o.d;
    
  }
};

int main() {
  cin.sync_with_stdio(false);

  int n, z, d, a;
  cin >> n >> z;
  multiset<Monster> m;
  
  for (int i = 0; i < n; ++i) {
    cin >> d >> a;
    m.insert(Monster(i, d, a));
  }
  
  for (multiset<Monster>::const_iterator i = m.begin(); i != m.end(); ++i) {
    //cout << "z: " << z << " d: " << i->d << " a: " << i->a << endl;
    
    if ((z -= i->d) <= 0) {
      cout << "NIE" << endl;
      return 0;
    }
    z += i->a;
  }
  
  cout << "TAK" << endl;
  int iter = m.size();
  for (multiset<Monster>::const_iterator i = m.begin(); 
       i != m.end(); ++i, --iter) {
    cout << (i->idx + 1);
    if (iter > 0) cout << " ";
  }
  cout << endl;
  return 0;
}