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
106
107
108
109
110
111
112
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue <pair <pair <long long int, long long int>, long long int> > qd;
priority_queue <pair <pair <long long int, long long int>, long long int> > qsz;
priority_queue <pair <pair <long long int, long long int>, long long int> > qsr;
vector <bool> v;
vector <long long int> wyn;

int main()
{
	long long int n, z, l1, l2, x;
	bool czy;
	
	scanf("%lld %lld", &n, &z);
	v.resize(n+1, 1);
	czy=true;
	x=0;
	
	for(long long int i=0;i<n;i++)
	{
	 scanf("%lld %lld", &l1, &l2);
	 
	 	if(l2-l1>=0)
	 		qd.push(make_pair(make_pair(-l1, l2-l1), i+1));
	 	else
	 		if(l2>0)
	 		{
	 		 qsz.push(make_pair(make_pair(l1, -l2), i+1));
	 		 qsr.push(make_pair(make_pair(l2-l1, l1), i+1));
	 		}
	 		else
	 		{
	 		 v[i+1]=2;
	 		 x=x+l1;
	 		}
	}
	
	while(!qd.empty())
	{
		if(z>-qd.top().first.first)
		{
	 	 z=z+qd.top().first.second;
	 	 wyn.push_back(qd.top().second);
	 	}
	 	else
	 	{
	 	 czy=false;
	 	 break;
	 	}
	 
	 v[qd.top().second]=0;		
	 qd.pop();
	}
	
	while(!qsz.empty() || !qsr.empty())
	{	
	 	if(z<=qsz.top().first.first)
	 	{
	 	 czy=false;
	 	 break;
	 	}
	 
	 	if(z+qsr.top().first.first>qsz.top().first.first)
	 	{
	 	 z=z+qsr.top().first.first;
	 	 v[qsr.top().second]=0;
	 	 wyn.push_back(qsr.top().second);
	 	 qsr.pop();
	 	}
	 	else
	 	{
	 	 z=z-qsz.top().first.first-qsz.top().first.second;
	 	 v[qsz.top().second]=0;
	 	 wyn.push_back(qsz.top().second);
	 	 qsz.pop();
	 	}
	 	
	 	while(!qsz.empty() && v[qsz.top().second]==0)
	 		qsz.pop();
	 		
	 	while(!qsr.empty() && v[qsr.top().second]==0)
	 		qsr.pop();
	}
	
	if(czy==true && z>x)
	{
		for(int i=1;i<v.size();i++)
			if(v[i]==2)
				wyn.push_back(i);
	}
	else
		czy=false;
	
	if(czy==false)
		printf("NIE\n");
	else
	{		
	 printf("TAK\n");
	 
	 	for(int i=0;i<wyn.size();i++)
	 		printf("%lld ", wyn[i]);
	}
	
	return 0;
}