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

struct Potwor {
	int s, b, n;
	Potwor(int _s, int _b, int _n) : s(_s), b(_b - _s), n(_n) {}
};

struct Porownaj {
	bool operator() (Potwor a, Potwor b) {
		if (a.s == b.s) {
			if (a.b == b.b) {
				return a.n < b.n;
			} else {
				return a.b > b.b;
			}
		} else {
			return a.s > b.s;
		}
	}
};

set<Potwor, Porownaj> P;
set<Potwor, Porownaj>::iterator it1, it2;
vector<int> K;

int main() {
	int e, p, s;
	long long z;
	scanf("%d %lld", &p, &z);
	for (int i = 0; i < p; ++i) {
		scanf("%d %d", &s, &e);
		P.insert(Potwor(s, e, i + 1));
	}
	for (set<Potwor, Porownaj>::iterator i = P.begin(); i != P.end();) {
		if (i->s < z && i->b > 0) {
			z += i->b;
			K.push_back(i->n);
			P.erase(i++);
		} else {
			++i;
		}
	}
	while (!P.empty()) {
		it1 = P.lower_bound(Potwor(z - 1, 100001, 0));
		if (it1 == P.end()) break;
		if (it1->b < 0) {
			it2 = P.lower_bound(Potwor(z + it1->b, 100001, 0));
			if (it2 != it1) it1 = --it2;
		}
		z += it1->b;
		K.push_back(it1->n);
		P.erase(it1);
	}
	if (P.empty()) {
		puts("TAK");
		for (int i = 0; i < (int)K.size(); ++i) printf("%d ", K[i]);
		puts("");
	} else {
		puts("NIE");
	}
	return 0;
}