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
#include <iostream>
#include <algorithm>
#define MAXN 100001
using namespace std;

struct monster
{
	int nr;
	int dam;
	int hpup;
};
		
monster good[MAXN], bad[MAXN];
		
bool Good(monster a, monster b)
{
	return a.dam < b.dam;
}

bool Bad(monster a, monster b)
{
	if(a.hpup > b.hpup)
	return true;
	else if (a.hpup == b.hpup && a.dam > b.dam)
	return true;
	else return false;
}
	

void quest()
{
	int n, z, d, c, j,k ;
	cin >> n >> z;
	j=0;
	k=0;
	for (int i = 0 ; i < n ; ++i)
	{
		cin >> d >> c;
		if ( d >= c )
		{
			bad[j].nr = i+1;
			bad[j].dam = d;
			bad[j].hpup = c;
			++j;
		}
		else 
		{
			good[k].nr = i+1;
			good[k].dam = d;
			good[k].hpup = c;
			++k;
		}
	}
	sort(good, good + k, Good);
	sort(bad, bad + j, Bad);
	for (int i = 0; i < k; ++i)
	{
		z -= good[i].dam;
		if(z<=0)
		{
			cout << "NIE";
			return;
		}
		z+= good[i].hpup;
	}

	for (int i = 0; i < j; ++i)
	{
		z -= bad[i].dam;
		if(z<=0)
		{
			cout << "NIE";
			return;
		}
		z+= bad[i].hpup;
	}
	cout << "TAK" << endl;
	for ( int i = 0; i < k; ++i)
	{
		cout << good[i].nr << " ";
	}
	for ( int i = 0; i < j; ++i)
	{
		cout << bad[i].nr << " ";
	}
}	
		
int main()
{
	quest();
	return 0;
}