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

using std::sort;

#define MONSTERS_COUNT 100000

inline int sign(int x)
{
  return (x > 0) - (x < 0);
}

struct Monster
{
  int damage;
  int aid;
};

Monster monsters[MONSTERS_COUNT];
int monstersIndex[MONSTERS_COUNT];

bool monstersLessOperator(int i1, int i2)
{
  Monster & m1 = monsters[i1];
  Monster & m2 = monsters[i2];

  int diff1 = m1.aid - m1.damage;
  int diff2 = m2.aid - m2.damage;

  int sign1 = sign(diff1);
  int sign2 = sign(diff2);

  if (sign1 != sign2)
    return sign1 > sign2;

  if (sign1 >= 0)
  {
    if (m1.damage != m2.damage)
      return m1.damage < m2.damage;

    return m1.aid > m2.aid;
  }
  else
  {
    if (m1.aid != m2.aid)
      return m1.aid > m2.aid;

    return m1.damage > m2.damage;
  }
}

int main()
{
  int n, z;
  scanf("%d%d", &n, &z);
  for (int m = 0; m < n; m++)
  {
    int d, a;
    scanf("%d%d", &d, &a);
    monsters[m].damage = d;
    monsters[m].aid = a;
    monstersIndex[m] = m;
  }

  sort(monstersIndex, monstersIndex + n, monstersLessOperator);
  for (int gm = 0; gm < n; gm++)
  {
    int i = monstersIndex[gm];
    Monster & m = monsters[i];
    z -= m.damage;
    if (z <= 0) {
      printf("NIE\n");
      return 0;
    }

    z += m.aid;
  }

  printf("TAK\n");
  for (int i = 0; i < n; i++)
    printf("%d ", monstersIndex[i] + 1);
  printf("\n");

  return 0;
}