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

set<pair<int, pair<int, int> > > s;
vector<pair<int, pair<int, int> > > v;
vector<int> WYNIK;
int n; int z;
bool FALSE;
void zrob_a (set<pair<int, pair<int, int > > > ::iterator  it)
{
	if(FALSE)
	return;
	set<pair<int, pair<int, int > > > ::iterator it2 = it;
	while(it!=s.begin())
	{
		it2=it;
		it2--;
		if(z + (*it).second.first <= (*it2).first )
		{
			zrob_a(it2);
		}
		else
		break;
		
	}
	if(z<= (*it).first)
	{
		FALSE = true;
	}
	if(FALSE)
	return;
	z = z+ (*it).second.first;
	WYNIK.push_back((*it).second.second);
	s.erase(it);
	return;
		
		
}

int main()
{
	 cin>>n>>z; FALSE=0;
	for(int i=0; i<n; i++)
	{
		int a,b; cin>>a>>b; 
		if( b-a >= 0)
		v.push_back( {a, {b-a, i+1} });
		else
		s.insert( {a, {b-a, i+1} } ) ;
	}
	sort(v.begin(), v.end() );
	for(int i=0; i<v.size(); i++){
		
		if(v[i].first >= z)
			{
				
				cout<<"NIE"<<endl;
				return 0;
			}
		else
			z+=v[i].second.first;
		WYNIK.push_back(v[i].second.second);
	}
	while(!s.empty())
	{
		set<pair<int, pair<int, int > > > ::iterator it  = s.end();
			it--;
		zrob_a(it);
		if(FALSE || z<=0)
		{
			cout<<"NIE"<<endl;
			return 0;
		}
	}
	cout<<"TAK"<<endl;
	for(int i=0; i<WYNIK.size(); i++)
	cout<<WYNIK[i]<<" ";
	cout<<endl;
}