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 <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct mon {
//	mon (int _d, int _a, int _n): d(_d), a(_a), n(_n) {}
	mon (int _n): n(_n) {}
	int d;
	int a;
	int n;
};

struct _cmp {
  bool operator() (mon* a, mon* b) { return (a->a < b->a);}
} cmp;

struct _cmp1 {
  bool operator() (mon* a, mon* b) { return ((a->a - a->d) < (b->a - b->d));}
} cmp1;


int main () {
	int n, i;
	long long int z;
	vector<mon*> pv, nv;
	vector<mon*>::iterator mvi;
	mon* m;
	
	cin >> n >> z;
	
	for (i = 1; i <= n; i++) {
		m = new mon (i);
		cin >> m->d >> m->a;
		if (m->a - m->d <= 0) {
			nv.push_back (m);
		} else {
			pv.push_back (m);
		}
//		cout << z << endl;
	}
	
	sort (pv.begin(), pv.end(), cmp);
	sort (nv.begin(), nv.end(), cmp1);
	
	bool  win = true;
	
	for (mvi = pv.begin (); mvi != pv.end(); mvi++) {
		//cout << z << " p: " << (*mvi)->n << " " << (*mvi)->d << " " << (*mvi)->a << endl;
		z = z - (*mvi)->d;
		if (z <= 0) win = false;
		z = z + (*mvi)->a;
	}
	for (mvi = nv.begin (); mvi != nv.end(); mvi++) {
		//cout << z << " n: " << (*mvi)->n << " " << (*mvi)->d << " " << (*mvi)->a << endl;
		z = z - (*mvi)->d;
		if (z <= 0) win = false;
		z = z + (*mvi)->a;		
	}

	if (win == true) {
		cout << "TAK\n";
		for (mvi = pv.begin (); mvi != pv.end(); mvi++) {
			cout << (*mvi)->n << " ";
		}
		for (mvi = nv.begin (); mvi != nv.end(); mvi++) {
			cout << (*mvi)->n << " ";
		}
	} else {
		cout << "NIE";
	}
	

	cout << endl;		
	
	return 0;
}