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

pair<pair<int,int>,int> t[2*V];
int t1[100010];
bool v;
long long z;
vector<pair<pair<int,int>,int> > Q;
queue<int> kol;

void update(int x)
{
	while(x>1)
	{
		x/=2;
		t[x]=max(t[2*x],t[2*x+1]);
	}
}

pair<pair<int,int>,int> mx(int p, int k, int k1, int x)
{
	//printf("%d %d %d %d\n", p, k, k1, x);
	if(k==k1) return t[x];

	int s=(p+k1)/2;
	if(k<=s) return mx(p,k,s,2*x);
	return max(mx(p,s,s,2*x),mx(s+1,k,k1,2*x+1));
}

int main()
{
	int n;
	scanf("%d%d", &n, &z);
	for(int i=0;i<n;i++)
	{
		int x,y;
		scanf("%d%d", &x, &y);
		Q.push_back(make_pair(make_pair(x,y-x),i+1));
	}
	sort(Q.begin(),Q.end());

	for(int i=0;i<=100000;i++) t1[i]=-1;
	for(int i=V;i<2*V;i++) t[i].first.first=-1000000;

	for(int i=0;i<n;i++)
	{
		t[V+i].first.first=Q[i].first.second;
		t[V+i].first.second=Q[i].second;
		t[V+i].second=i;
		t1[Q[i].first.first]=i;
	}
	int x=-1;
	for(int i=0;i<=100000;i++)
	{
		if(t1[i]!=-1) x=t1[i];
		else t1[i]=x;
	}

	x=V/2;
	while(x>0){
		for(int i=x;i<2*x;i++)
			t[i]=max(t[2*i],t[2*i+1]);
		x/=2;
	}

	for(int i=0;i<n;i++)
	{
		if(t1[z]==-1){
			printf("NIE\n");
			return 0;
		}
		pair<pair<int,int>,int> c=mx(0,t1[z],V-1,1);

		if(c.first.first==-1000000){
			printf("NIE\n");
			return 0;
		}
		//printf("%d %d %d\n", c.first.first, c.first.second, c.second);
		kol.push(c.first.second);
		z+=c.first.first;
		t[V+c.second].first.first=-1000000;
		update(V+c.second);

	}

	printf("TAK\n");
	while(!kol.empty())
	{
		printf("%d ", kol.front());
		kol.pop();
	}
}