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

using namespace std;

struct triple {
  int a,b,id;
};

vector<int> result; 
vector<triple> pos,neg;
triple t;

bool check(long long z) {
  for(int i=0; i<pos.size(); i++)
    if(z<=pos[i].a) return false;
    else {
      z+=pos[i].b;
      result.push_back(pos[i].id);
    }
    
  for(int i=0; i<neg.size(); i++)
    if(z<=neg[i].a) return false;
    else {
      z+=neg[i].b;
      result.push_back(neg[i].id);
    }
  
  return true;
}

bool poscmp(const triple &t1, const triple &t2) {
  if(t1.a==t2.a) 
    return t1.b < t2.b;

  return t1.a < t2.a;
}

bool negcmp(const triple &t1, const triple &t2) {
  if(t1.a==t2.a) 
    return t1.b < t2.b;
    
  return t1.a > t2.a;
}

int main(int argc, char *argv[]) {  
  int n,z,a,b;
  
  scanf("%d%d", &n, &z);
  for(int i=0; i<n; i++) {
    scanf("%d%d", &a, &b);
    t.a=a; t.b=b-a; t.id=i+1;
    if(t.b>=0) pos.push_back(t);
    else neg.push_back(t);
  }
  
  sort(pos.begin(), pos.end(), poscmp);
  sort(neg.begin(), neg.end(), negcmp);
  
  if(check(z)) {
    puts("TAK");
    for(int i=0; i<result.size(); i++)
      printf("%d ", result[i]);
    puts("");
  }
  else puts("NIE");
  
  return 0;
}