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 <sstream>
#include <algorithm>
	
using namespace std;

class positive
{public:
    int it;
    int d, a;
    bool operator < (const positive& other ) const {return d<other.d;}
    positive (int _it,int _d,int _a):it(_it),d(_d),a(_a){}
};
class negative
{public:
    int it;
    int d, a;
    bool operator < (const negative& other ) const {return (a+d)>=(other.a+other.d);}
    negative(int _it,int _d,int _a):it(_it),d(_d),a(_a){}
};

int main () {
	cin.sync_with_stdio(false);
	int n, z;
	cin >> n >> z;
	int d, a;
	vector<positive> pos;
	vector<negative> neg;
	pos.reserve(n);
	neg.reserve(n);
 
	ostringstream out;
	int sum = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> d >> a;
		a -= d;
		sum += a;
		if (a >= 0) {
			pos.emplace_back(i, d, a);
		} else {
			neg.emplace_back(i, d, a);
		}
	}
	
	if ((z + sum) <= 0) {
		cout << "NIE";
		return 0;
	} else {
		sort(pos.begin(), pos.end());
		sort(neg.begin(), neg.end());
		
		for(size_t i = 0; i < pos.size(); ++i) {
			positive enemy = pos[i];
			if (z - enemy.d <= 0) {
				cout << "NIE";
				return 0;
			} else {
				z += enemy.a;
				out << enemy.it << " ";
			}
		}
		
		for(size_t i = 0; i < neg.size(); ++i) {
			negative enemy = neg[i];
			if (z - enemy.d <= 0) {
				cout << "NIE";
				return 0;
			} else {
				z += enemy.a;
				out << enemy.it << " ";
			}
		}
		
	}
	cout << "TAK" << endl << out.str();
	return 0;
}