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


//# dla m > 0 posortwowac rosonaco po d i probowac przyjmowac po kolei
//# dla m <= 0 posortowac rosnaco po m i probowac przyjmowac po kolei

using namespace std;

struct potwor{
	int d; // obrazenia
	int a; // moc eliksiru
	int m; // roznica miedzy moca eliksiru a liczba obrazen
	int idx;
};

bool compd (potwor p1, potwor p2) {
 	return (p1.d < p2.d);
}

bool compm (potwor p1, potwor p2) {
 	return (p2.m > p1.m);
}

int main(){
	ios_base::sync_with_stdio(0);

	long long int n, z, d, a, tmpz;

	cin >> n >> z;
	tmpz = z;

	vector<potwor> dodatnie;
	vector<potwor> ujemne;
	dodatnie.reserve(n);
	ujemne.reserve(n);

	for(int i=1; i<=n; i++){
		cin >> d >> a;
		potwor p;
		p.a = a;
		p.d = d;
		p.m = a-d;
		p.idx = i;
		z += p.m;
		if(p.m >= 0)
			dodatnie.push_back(p);
		else
			ujemne.push_back(p);
	}

	if(z <= 0){
		cout << "NIE" << endl;
	}
	else{
		z = tmpz;
		vector<int> kolejnosc;

		sort(dodatnie.begin(), dodatnie.end(), compd);
		sort(ujemne.begin(), ujemne.end(), compm);

		vector<potwor>::iterator it;

		for(it=dodatnie.begin();it!=dodatnie.end();it++){
			if(it->d >= z){
				cout << "NIE" << endl;
				return 0;
			}
			z += it->m;
			kolejnosc.push_back(it->idx);
		}

		for(it=ujemne.begin();it!=ujemne.end();it++){
			if(it->d >= z){
				cout << "NIE" << endl;
				return 0;
			}
			z += it->m;
			kolejnosc.push_back(it->idx);
		}

		cout << "TAK" << endl;
		vector<int>::iterator it2;
		for(it2=kolejnosc.begin(); it2!=kolejnosc.end(); it2++){
			cout << *it2 << ' ';
		}
		cout << endl;

	}
	
	return 0;
}