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

using namespace std;

class Monster {
public:
   long nr;
   long damage;
   long life;

   Monster() : nr(0L), damage(0L), life(0L) {}
   Monster(long n, long d, long l) : nr(n), damage(d), life(l) {}

};

struct lowDamage {
   bool operator() (const Monster& lhc, const Monster& rhc) const
   {
      if(lhc.damage < rhc.damage)
         return true;
      else if(lhc.damage == rhc.damage)
      {
         if(lhc.life > rhc.life)
            return true;
      }

      return false;
   }
};

struct highDamage {
   bool operator() (const Monster& lhc, const Monster& rhc) const
   {
      if(lhc.damage > rhc.damage)
         return true;
      else if(lhc.damage == rhc.damage)
      {
         if(lhc.life > rhc.life)
            return true;
      }

      return false;
   }
};

multiset<Monster, lowDamage> setCoolMonsters;
multiset<Monster, highDamage> setUglyMonsters;
vector<long> vecNrs;

bool CheckCoolMonsters(long& prevlife)
{
   multiset<Monster, lowDamage>::iterator itCool = setCoolMonsters.begin();
   while(itCool != setCoolMonsters.end())
   {
      if(itCool->damage >= prevlife)
         return false;
      prevlife += itCool->life;
      vecNrs.push_back(itCool->nr);
      ++itCool;
   }
   return true;
}

bool CheckUglyMonsters(long& prevlife)
{
   multiset<Monster, highDamage>::iterator itUgly = setUglyMonsters.begin();
   while(itUgly != setUglyMonsters.end())
   {
      if(itUgly->damage >= prevlife)
         return false;
      prevlife += itUgly->life;
      vecNrs.push_back(itUgly->nr);
      ++itUgly;
   }
   return true;
}

int main(int argc, char* argv[])
{
   long  monsters = 0L;
   long  life = 0L;
   long  cd = 0L;
   long  cl = 0L;

   scanf("%ld %ld\n", &monsters, &life);
   vecNrs.reserve(monsters);

   for (long idx = 1L; idx <= monsters; ++idx)
   {
      scanf("%ld %ld\n", &cd, &cl);
      if(cd <= cl)
         setCoolMonsters.insert(Monster(idx, cd, cl - cd));
      else
         setUglyMonsters.insert(Monster(idx, cd, cl - cd));
   }

   bool isok = CheckCoolMonsters(life);
   if(isok)
      isok = CheckUglyMonsters(life);
   if(isok)
   {
      printf("TAK\n");
      vector<long>::const_iterator vit = vecNrs.begin();
      while(vit != vecNrs.end())
      {
         cout << *vit << " ";
         ++vit;
      }
   }
   else
      printf("NIE\n");
  
   return 0;
}