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

using namespace std;

#define M 100005

long long D[M];
long long A[M];
long long B[M];

class BalanceComparator {
	public:
	bool operator() (const int& a, const int& b) {
		if (D[a] == 0) return false;
		if (D[b] == 0) return true;
		return (B[a] * D[b]) < (B[b] * D[a]);
	}
};

class DamageComparator {
	public:
	bool operator() (const int& a, const int& b) {
		return D[a] > D[b];
	}
} dmgcmp;


int main() {
	long long z;
	int n;
	scanf("%d%lld",&n,&z);
	vector<int> strongs;
	vector<int> solution;
	priority_queue<int, vector<int>, BalanceComparator> weaks;
	for (int i = 0; i < n; i++) {
		scanf("%lld%lld", &D[i], &A[i]); B[i] = A[i] - D[i];
	}

	for (int i = 0; i < n; i++) {
		if (D[i] < z || D[i] == 0) weaks.push(i);
		else strongs.push_back(i);
	}

	sort(strongs.begin(), strongs.end(), dmgcmp);
	//for (vector<int> :: iterator it = strongs.begin(); it != strongs.end(); it++) printf("%lld %lld\n", D[*it], A[*it]);

	bool omg = true;
	while (!weaks.empty()) {
		int top = weaks.top(); weaks.pop();
		// printf("monster nr %d: %lld %lld with balance %lld/%lld\n", top+1, D[top], A[top], B[top], D[top]);
		if (z <= D[top] && D[top] != 0) omg = false;
		z += B[top];
		solution.push_back(top);
		//printf("mam hp: %lld\n", z);
		//printf("strongs size: %d\n", strongs.size());
		//printf("strongs back: %lld %lld\n", D[strongs.back()], A[strongs.back()]);
		while (!strongs.empty() && D[strongs.back()] < z) {
			int back = strongs.back();
			//printf("dodaje %lld %lld\n", D[back], A[back]);
			weaks.push(back);
			strongs.pop_back();
		}
	}
	if (weaks.empty() && strongs.empty() && omg) {
		printf("TAK\n");
		for (vector<int> :: iterator it = solution.begin(); it != solution.end(); it++) {
			printf("%d ", *it + 1);
		}
		printf("\n");
	} else {
		printf("NIE\n");
	}	


	return 0;
}