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
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>

//#define DEBUG

#ifdef DEBUG
#define D(...) __VA_ARGS__
#else
#define D(...)
#endif

using namespace std;

struct Monster
{
	int i;
	int d;
	int a;
};

bool cmp_d(const Monster &a, const Monster &b)
{
	return a.d < b.d;
};

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

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	long long z;
	cin >> n >> z;

	vector<Monster> pos, neg;

	for(int i=0; i<n; i++)
	{
		Monster m;
		m.i = i+1;
		cin >> m.d >> m.a;
		assert(0 <= m.d);
		assert(m.d <= 100000);
		assert(0 <= m.a);
		assert(m.a <= 100000);
		D(cerr << "i: " << m.i << ", d: " << m.d << ", a: " << m.a << endl;)
		if(m.a >= m.d)
		{
			pos.push_back(m);
		}
		else
		{
			neg.push_back(m);
		}
	}
	sort(pos.begin(), pos.end(), &cmp_d);

	D(cerr << "Starting hp: " << z << endl;)
	vector<int> order;

	for(auto &m: pos)
	{
		if(z > m.d)
		{
			z = z - m.d + m.a;
			D(cerr << "Killing " << m.i << ", hp: " << z << endl;)
			order.push_back(m.i);
		}
		else
		{
			D(cerr << "Not enough hp to kill " << m.i << "!" << endl;)
			cout << "NIE" << endl;	
			return 0;
		}
	}
	sort(neg.begin(), neg.end(), &rcmp_a);
	for(auto &m: neg)
	{
		if(z > m.d)
		{
			z = z - m.d + m.a;
			D(cerr << "Killing " << m.i << ", hp: " << z << endl;)
			order.push_back(m.i);
		}
		else
		{
			D(cerr << "Not enough hp to kill " << m.i << "!" << endl;)
			cout << "NIE" << endl;	
			return 0;
		}
	}
	cout << "TAK" << endl;
	for(auto o: order)
	{
		cout << o << " ";
	}
	cout << endl;

	return 0;
}