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
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

struct monster {
  int d_, a_, idx_;
  monster(int d, int a, int idx) : d_(d), a_(a), idx_(idx) {}
  
  bool operator< (const monster& x) const {
    if (d_ == x.d_) {
      if (a_ == x.a_) {
        return idx_ < x.idx_;
      }
      return a_ > x.a_;
    }
    return d_ < x.d_;
  }

  bool operator> (const monster& x) const {
    if (a_ == x.a_) {
      if (d_ == x.d_) {
        return idx_ < x.idx_;
      }
      return d_ > x.d_;
    }
    return a_ > x.a_;
  }
};

vector<monster> pos, neg;

int main() {
  int n;
  long long z;
  scanf("%d%lld", &n, &z);

  vector<int> wyn;
  for (int i = 0; i < n; i++) {
    int d, a;
    scanf("%d%d", &d, &a);

    if (d <= a) {
      pos.push_back(monster(d, a, i + 1));
    } else {
      neg.push_back(monster(d, a, i + 1));
    }
  }

  sort(pos.begin(), pos.end(), std::less<monster>());
  sort(neg.begin(), neg.end(), std::greater<monster>());

  for (int i = 0; i < pos.size(); i++) {
    if (z <= pos[i].d_) {
      printf("NIE\n");
      return 0;
    }

    z += (pos[i].a_ - pos[i].d_);
    wyn.push_back(pos[i].idx_);
  }

  for (int i = 0; i < neg.size(); i++) {
    if (z <= neg[i].d_) {
      printf("NIE\n");
      return 0;
    }

    z -= (neg[i].d_ - neg[i].a_);
    wyn.push_back(neg[i].idx_);
  }

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

  return 0;
}