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

typedef long long ll;
const int MAXN = 100010;
//pair< ll, ll > monstersInc[MAXN];
//pair< ll, ll > monstersDec[MAXN];

struct monster {
  ll d;
  ll a;
  int ind;
};
monster monstersInc[MAXN];
monster monstersDec[MAXN];

bool cmp1(const monster& m1, const monster& m2) {
  return m1.d < m2.d;
}
bool cmp2(const monster& m1, const monster& m2) {
  return m1.a > m2.a;
}

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

  ll d, a;
  int incInd = 0;
  int decInd = 0;
  for(int i = 0; i < n; i++) {
    scanf("%lld %lld", &d, &a);

    if(-d + a > 0) {
      monstersInc[incInd].d = d;
      monstersInc[incInd].a = a;
      monstersInc[incInd].ind = i+1;
      incInd++;
    } else {
      monstersDec[decInd].d = d;
      monstersDec[decInd].a = a;
      monstersDec[decInd].ind = i+1;
      decInd++;
    }
  }

  sort(monstersInc, monstersInc+incInd, cmp1);
//  printf("inc:\n");
//  for(int i = 0; i < incInd; i++) {
//    printf("%d: %lld %lld\n", monstersInc[i].ind, monstersInc[i].d, monstersInc[i].a);
//  }
  sort(monstersDec, monstersDec + decInd, cmp2);
//  printf("\n");
//  printf("dec:\n");
//  for(int i = 0; i < decInd; i++) {
//    printf("%d: %lld %lld\n", monstersDec[i].ind, monstersDec[i].d, monstersDec[i].a);
//  }
//  printf("\n");

  bool impossible = false;

  for(int i = 0; i < incInd; i++) {
    z -= monstersInc[i].d;
    if(z <= 0) {
      impossible = true;
      break;
    }
    z += monstersInc[i].a;
  }

  if(impossible == false) {
    for(int i = 0; i < decInd; i++) {
      z -= monstersDec[i].d;
      if(z <= 0) {
        impossible = true;
        break;
      }
      z += monstersDec[i].a;
    }
  }

  if(impossible == false) {
    printf("TAK\n");
    for(int i = 0; i < incInd; i++) {
      printf("%d ", monstersInc[i].ind);
    }
    for(int i = 0; i < decInd; i++) {
      printf("%d ", monstersDec[i].ind);
    }
    printf("\n");
  } else {
    printf("NIE\n");
  }

  return 0;
}