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
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <memory>

using namespace std;

struct monster_t {
  int i, d, a;
  monster_t(int i, int d, int a): i(i), d(d), a(a) {}
};


int main() {
  ios_base::sync_with_stdio(false);
  int monsters_count, hp;

  list<monster_t> in_plus, in_minus;
  vector<int> answer;
  
  cin >> monsters_count >> hp;
  answer.reserve(monsters_count);
  
  for (int i = 0 ; i < monsters_count ; ++i) {
    int d, a;
    cin >> d >> a;
    if (a >= d) {
      in_plus.emplace_back(i + 1, d, a);
    } else {
      in_minus.emplace_back(i + 1, d, a);
    }
  }

  in_plus.sort([](const monster_t &a, const monster_t &b) {
      return a.d < b.d;
    });
  in_minus.sort([](const monster_t &a, const monster_t &b) {
      return a.a > b.a
          || (a.a == b.a && a.d < b.d);
    });

  in_plus.splice(in_plus.end(), move(in_minus));
  
  while (!in_plus.empty()) {
    auto monster = in_plus.front();
    in_plus.pop_front();
    if (monster.d >= hp) {
      cout << "NIE\n";
      return 0;
    } else {
      hp += (monster.a - monster.d);
      answer.push_back(monster.i);
    }
  }

  if (hp > 0) {
    cout << "TAK\n";
    for(const auto &i : answer) {
      cout << i << ' ';
    }
  } else {
    cout << "NIE\n";
  }
  
  return 0;
}