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
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

typedef long long LL;
const int MX = 1e5 + 100;
LL a[MX], d[MX], n, z;
vector<LL> v;
struct cmp_plusy
{
	bool operator()(const LL x, const LL y)
	{
		if(d[x] != d[y])
			return d[x] > d[y];
		return x > y;
	}
};
struct cmp_minusy
{
	bool operator()(const LL x, const LL y)
	{
		if(a[x] != a[y])
			return a[x] < a[y];
		return x > y;
	}
};
priority_queue<LL, vector<LL>, cmp_plusy> plusy;
priority_queue<LL, vector<LL>, cmp_minusy> minusy;

int main()
{
	scanf("%lld%lld", &n, &z);
	for(int i = 1; i <= n; ++ i)
	{
		scanf("%lld%lld", &d[i], &a[i]);
		if(a[i] - d[i] >= 0)
			plusy.push(i);
		else
			minusy.push(i);
	}
	
	while(!plusy.empty())
	{
		LL u = plusy.top();
		plusy.pop();	
		if(z <= d[u])
		{
			puts("NIE");
			return 0;
		}
		z -= d[u];
		z += a[u];
		v.push_back(u);
	}

	while(!minusy.empty())
	{
		LL u = minusy.top();
		minusy.pop();
		if(z <= d[u])
		{
			puts("NIE");
			return 0;
		}
		z -= d[u];
		z += a[u];
		v.push_back(u);
	}

	puts("TAK");
	for(int i = 0; i < v.size(); ++ i)
		printf("%lld ", v[i]);
	printf("\n");

	return 0;
}