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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//#define dump(...) cerr << #__VA_ARGS__ << __VA_ARGS__ << endl
#define dump(...)
typedef unsigned long long u64;
typedef long long i64;

struct Boss
{
	static unsigned NumInstances;
	unsigned id;
	u64 dmg;
	u64 rev;
	i64 balance() const
	{
		return rev - dmg;
	}
	bool positive() const
	{
		return this->balance() > 0;
	}
	bool operator<(Boss const & other) const
	{
		if (this->positive() != other.positive())
			return this->positive();
		if (this->positive())
		{
			if (this->dmg == other.dmg)
				return this->balance() > other.balance();
			else
				return this->dmg < other.dmg;
		}
		else
		{
			if (this->dmg == other.dmg)
				return this->balance() > other.balance();
			else
				return this->dmg > other.dmg;
//			if (this->balance() == other.balance())
//				return this->dmg < other.dmg;
//			else
//				return this->balance() > other.balance();
		}
	}
};

unsigned Boss::NumInstances = 0;

ostream & operator<<(ostream & os, Boss const & boss) { return os << boss.id; }
istream & operator>>(istream & is, Boss & boss) { boss.id = ++Boss::NumInstances; return is >> boss.dmg >> boss.rev; }

int main()
{
	int n;
	u64 z;
	cin >> n >> z;
	vector<Boss> bosses(n);
	for (int i = 0; i < n; i++)
	{
		cin >> bosses[i];
	}
	sort(bosses.begin(), bosses.end());
	vector<Boss>::const_iterator const begin = bosses.begin(), end = bosses.end();
	vector<Boss>::const_iterator iter = begin;
	do
	{
		Boss const & boss = *iter;
dump(boss.id << boss.dmg << boss.rev); 
		if (boss.dmg >= z)
		{
			cout << "NIE\n";
			return 0;
		}
		z += boss.balance();
	}
	while (++iter != end);
	iter = begin;
	cout << "TAK\n" << iter->id;
	while (++iter != end)
	{
		cout << " " << iter->id;
	}
	cout << "\n";
}