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
#include <cstdio>
#include <list>
#include <vector>

//#define DEBUG 1

#ifdef DEBUG
#define debug(x...) printf(x)  
#else
#define debug(x...)  
#endif

class Monster 
{
public:
	int id; 
	int d; 
	int a; 
	int gain() const { return a-d;}
	bool operator < (const Monster & other);
};

//Define gain as a balance between healing fluid and monster damage
//Sorting monsters to get the following order:
//First the ones with non-negative gain, with damage ascending
//Next the ones with negative gain, with heal descending
bool Monster::operator < (const Monster & other)
{
	if (this->gain() >= 0 && other.gain() >= 0)
	{
		return this->d < other.d;
	}
	else if (this->gain() < 0 && other.gain() >= 0)
	{
		return false;
	}
	else if (this->gain() >= 0 && other.gain() < 0)
	{
		return true;
	}
	else if (this->gain() < 0 && other.gain() < 0)
	{
		return this->a > other.a;
	}
}

typedef std::list<Monster> MonsterList;

MonsterList monsters;
std::vector<int> monstersOrder;

int main()
{
	int n;
	long long int z;
	scanf("%d %lld", &n, &z);
	
	//Monster *monsters = new Monster [n];
	
	for (int i = 1; i <= n; ++i)
	{
		Monster tmp;
		scanf("%d %d", &(tmp.d), &(tmp.a));
		tmp.id = i;
		monsters.push_back(tmp);
	}
	
	monsters.sort();
#ifdef DEBUG
	for (MonsterList::iterator it = monsters.begin(); it != monsters.end(); ++it)
	{
		printf("{%d: d=%d, a=%d}\n", it->id, it->d, it->a);
	}
#endif
	
	while (!monsters.empty())
	{
		bool found = false;
		debug("z = %lld\n", z);
		for (MonsterList::iterator it = monsters.begin(); it != monsters.end(); ++it)
		{
			debug("Checking monster of id=%d...\n", it->id);
			if (z - it->d <= 0) continue;
			debug("Checking monster of id=%d... OK\n", it->id);
			found = true;
			monstersOrder.push_back(it->id);
			z += it->a - it->d;
			monsters.erase(it);
			break;
		}
		if (!found)
		{
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	for (std::vector<int>::iterator it = monstersOrder.begin(); it != monstersOrder.end(); ++it)
	{
		printf("%d ", *it);
	}
	printf("\n");
	return 0;
}