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
//#define DEBUG

#include <algorithm>
#include <cstdio>
#include <vector>

#ifdef DEBUG
#define tracef(fmt, ...) \
        do { printf("%s:%d:%s(): " fmt "\n", __FILE__, \
                                __LINE__, __func__, ## __VA_ARGS__); } while (0)
#else
#define tracef(fmt, ...)
#endif

using namespace std;

struct Monster
{
  Monster() {}
  Monster(int id, int damage, int potion) : id(id), damage(damage), potion(potion) {}
  int id;
  int damage;
  int potion;
  int hpGain() const
  {
    return potion - damage;
  }
  bool isProfitable() const
  {
    return hpGain() >= 0;
  }
};

bool sort_cmp_damage_asc(const Monster& a, const Monster& b)
{
  return a.damage < b.damage;
}

bool sort_cmp_potion_desc(const Monster& a, const Monster& b)
{
  return a.potion > b.potion;
}

bool kill_monsters(const vector<Monster>& monsters, vector<int>& result, long long int& hp)
{
  for (int i = 0; i < monsters.size(); i++)
  {
    tracef("Killing monster with %d damage and %d potion reward. You have %d hp", monsters[i].damage, monsters[i].potion, (int)hp);
    if (hp <= monsters[i].damage)
    {
      tracef("Failed to kill.");
      return false;
    }
    hp += monsters[i].hpGain();
    tracef("Succesfully killed.");
    result.push_back(monsters[i].id);
  }

  return true;
}

int main()
{
  int n, startHp;
  scanf("%d%d", &n, &startHp);
  vector<Monster> profitableMonsters, lossyMonsters;
  vector<int> ret;
  ret.reserve(n);
  profitableMonsters.reserve(n);
  lossyMonsters.reserve(n);
  for (int id = 1; id <= n; id++)
  {
    int dmg, potion;
    scanf("%d%d", &dmg, &potion);
    Monster m(id, dmg, potion);
    if (m.isProfitable())
    {
      profitableMonsters.push_back(m);
    }
    else
    {
      lossyMonsters.push_back(m);
    }
  }

  long long int hp = startHp;
  tracef("Profitable:");
  sort(profitableMonsters.begin(), profitableMonsters.end(), sort_cmp_damage_asc);
  if (!kill_monsters(profitableMonsters, ret, hp))
  {
    printf("NIE\n");
    return 0;
  }

  tracef("Lossy:");
  sort(lossyMonsters.begin(), lossyMonsters.end(), sort_cmp_potion_desc);
  if (!kill_monsters(lossyMonsters, ret, hp))
  {
    printf("NIE\n");
    return 0;
  }

  if (ret.size() != n)
  {
    tracef("Result has bad size!");
  }
  printf("TAK\n");
  printf("%d", ret[0]);
  for (int i = 1; i < ret.size(); i++)
  {
    printf(" %d", ret[i]);
  }
  printf("\n");
  return 0;
}