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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <stdlib.h>
//---===---
#include <stdio.h>
#include <unistd.h>

typedef unsigned int uint;

char buf_in[4096000];
int buf_in_head = 0;
int buf_in_tail = 0;

static int getChar(void) {
  while (buf_in_head == buf_in_tail) {
    int rv = read(0, buf_in, sizeof(buf_in));
    if (rv > 0) {
      buf_in_head = 0;
      buf_in_tail = rv;
      break;
    };
    if (rv == 0) return EOF;
  }
  return buf_in[buf_in_head++];
}

// only 1 call is safe, and only if previously getChar() had been called.
static void ungetChar(void) {
  --buf_in_head;
}

static uint getUInt() {
  uint v;
  int c;
  for (;;) {
    c = getChar();
    if (c < '0') continue;
    if (c > '9') continue;
    v = c - '0';
    break;
  };
  for (;;) {
    c = getChar();
    if (c < '0') break;
    if (c > '9') break;
    v *= 10;
    v += c - '0';
  };
  ungetChar();
  return v;
}
//---===---

typedef struct {
  int d, a, i;
} tt;

tt T[100000];

int cmp(const tt * x, const tt * y) {
  int xd = -x->d + x->a;
  int yd = -y->d + y->a;

  if (xd >= 0) if (yd < 0) return -1; // healers before killers
  if (xd < 0) if (yd >= 0) return +1; // killers after healers

  if (xd >= 0) {
    // 2 healers, least damage first
    if (x->d < y->d) return -1;
    if (x->d > y->d) return +1;
  } else {
    // 2 killers, most healing first, so we stay as healthy as possible
    if (x->a > y->a) return -1;
    if (x->a < y->a) return +1;
  };

  // who cares
  if (x->i < y->i) return -1;
  if (x->i > y->i) return +1;
  return 0;
}

int void_cmp(const void * x, const void * y) {
  return cmp((const tt*)x, (const tt*)y);
}

int main (void) {
  int n, z;
  long long s;
  int i;

  // 1 <= n, z <= 100,000
  n = getUInt();
  z = getUInt();

  s = z;

  for (i = 0; i < n; ++i) {
    // 0 <= d, a <= 100,000
    T[i].d = getUInt(); s -= T[i].d;
    T[i].a = getUInt(); s += T[i].a;
    T[i].i = i + 1;
  };

  if (s <= 0) {
    printf("NIE\n");
    return 0;
  };

  qsort(T, n, sizeof(tt), void_cmp);

  s = z;

  for (i = 0; i < n; ++i) {
    s -= T[i].d;
    if (s <= 0) { printf("NIE\n"); return 0; };
    s += T[i].a;
  };

  printf("TAK\n%d", T[0].i);
  for (i = 1; i < n; ++i) printf(" %d", T[i].i);
  putchar('\n');

  return 0;
}