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
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <algorithm>
#include <iostream>
using namespace std;

const int SIZE = 1 + 100000;

struct Monster {
  int number;
  int cost;
  int profit;
  int balance;
  friend bool operator<(const Monster& lhs, const Monster& rhs) {
    if(lhs.balance >= 0) {
      if(rhs.balance < 0)
        return true;
      return lhs.cost < rhs.cost;
    }
    if(rhs.balance >= 0)
      return false;
    return lhs.profit > rhs.profit;
  }
};

Monster monster[SIZE];

int main() {
  ios_base::sync_with_stdio(0);
  int n;
  long long z;
  cin >> n >> z;
  for(int i = 1; i <= n; ++i) {
    monster[i].number = i;
    cin >> monster[i].cost >> monster[i].profit;
    monster[i].balance = monster[i].profit - monster[i].cost;
  }
  sort(monster + 1, monster + n + 1);
  bool result = true;
  for(int i = 1; i <= n; ++i) {
    if(z > monster[i].cost)
      z += monster[i].balance;
    else {
      result = false;
      break;
    }
  }
  if(result) {
    cout << "TAK\n";
    for(int i = 1; i < n; ++i)
      cout << monster[i].number << ' ';
    cout << monster[n].number << endl;
  }
  else
    cout << "NIE" << endl;
  return 0;
}