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
#include <iostream>
#include <utility>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
typedef long long LL;

struct Monster {
  int number;
  LL damage, potion;
  Monster(int n=0, LL d=0, LL p=0) : number(n), damage(d), potion(p) {}
  bool operator<(const Monster& other) const {
    if (damage != other.damage) {
      return damage < other.damage;
    }
    if (potion != other.potion) {
      return potion < other.potion;
    }
    return number < other.number;
  }
};
typedef vector<Monster> VM;

bool check(LL &live, VM monsters) {
  if (live <= 0) {
    return false;
  }
  sort(monsters.begin(), monsters.end());
  for (Monster m : monsters) {
    if (m.damage >= live) {
      return false;
    }
    live = live - m.damage + m.potion;
  }
  return true;
}

void solve() {
  int n;
  LL z;
  assert(2 == scanf("%d%lld", &n, &z));
  VM good, bad;
  LL endLive = z;
  for (int i = 0; i < n; ++i) {
    LL d, p;
    assert(2 == scanf("%lld%lld", &d, &p));
    Monster m(i + 1, d, p);
    endLive = endLive - m.damage + m.potion;
    if (m.damage < m.potion) {
      good.push_back(m);
    } else {
      bad.push_back(Monster(m.number, m.potion, m.damage));
    }
  }
  if (check(z, good) and check(endLive, bad)) {
    printf("TAK\n");
    for (Monster m : good) {
      printf("%d ", m.number);
    }
    reverse(bad.begin(), bad.end());
    for (Monster m : bad) {
      printf("%d ", m.number);
    }
    printf("\n");
  } else {
    printf("NIE\n");
  }
}

int main() {
  solve();
  return 0;
}