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
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <sstream>

struct CreatureInfo
{
	CreatureInfo(long idx, long a, long d)
		: idx(idx), a(a), d(d){}

	long a;
	long d;
	long idx;
};

bool CheckSubCollection(std::vector<CreatureInfo>& col, long long& z, std::stringstream& ss)
{
	for(auto& it : col)
	{
		z -= it.d;
		if(z <= 0)
		{
			return false;
		}

		z += it.a;
		ss << it.idx << " ";
	}

	return true;
}

int main()
{
	long n, z, a, d;
	scanf("%ld", &n);
	scanf("%ld", &z);

	std::vector<CreatureInfo> positive;
	positive.reserve(n);
	std::vector<CreatureInfo> zero;
	zero.reserve(n);
	std::vector<CreatureInfo> negative;
	negative.reserve(n);

	long long currZ = z;

	for(int i = 1; i<=n; ++i)
	{
		scanf("%ld", &d);
		scanf("%ld", &a);
		long result = a - d;
		currZ += result;

		if(result < 0)
			negative.push_back(CreatureInfo(i, a, d));
		else if(result == 0)
			zero.push_back(CreatureInfo(i, a, d));
		else
			positive.push_back(CreatureInfo(i, a, d));
	}

	long long startZ = z;
	std::stringstream ss;

	if(currZ <= 0)
		printf("NIE\n");
	else
	{
		std::sort(
			positive.begin(), 
			positive.end(), 
			[&](const CreatureInfo& l, const CreatureInfo& r)->bool 
			{ 
				return l.d < r.d; 
			} );

		std::sort(
			negative.begin(), 
			negative.end(), 
			[&](const CreatureInfo& l, const CreatureInfo& r)->bool 
			{ 
				if(l.d == r.d)
					return l.a > r.a;
				else
					return l.d > r.d; 
			} );
		
		if( CheckSubCollection(positive, startZ, ss) &&
			CheckSubCollection(zero, startZ, ss) &&
			CheckSubCollection(negative, startZ, ss))
		{
			printf("TAK\n");
			printf("%s", ss.str().c_str());
		}
		else
			printf("NIE\n");
	}
}