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

int n,z;

struct s {
	int diff;
	int cost;
	int index;
};

struct compare_diff {
	bool operator()(const s &value1, const s &value2) {
		return value1.diff > value2.diff;
	}
} dist_comparator;

struct compare_cost {
	bool operator()(const s &value1, const s &value2) {
		return value1.cost < value2.cost;
	}
} cost_comparator;

s monsters[100002];

int main() {
	scanf("%d %d", &n, &z);
	for (int i=0; i<n; i++) {
		scanf("%d %d", &monsters[i].cost, &monsters[i].diff);
		monsters[i].diff -= monsters[i].cost;
		monsters[i].index = i + 1;
	}
	
	sort(monsters, monsters + n, dist_comparator);
	
	int d;
	for (int i=0; i<n-1; i++) {
		if ( monsters[i].diff >= 0 && monsters[i+1].diff < 0) d = i + 1;
	}
//	for (int i=0; i<n; i++) {
//		printf("cost:%d, diff:%d\n", monsters[i].cost, monsters[i].diff);
//	}
//	printf("%d\n", d);
	
	if (d < n) {
		sort(monsters, monsters + d, cost_comparator);
		sort(monsters + d, monsters + n, cost_comparator);
		reverse(monsters + d, monsters + n);
	}
	
//	for (int i=0; i<n; i++) {
//		printf("%d: cost:%d, diff:%d\n", monsters[i].index, monsters[i].cost, monsters[i].diff);
//	}
	
	for (int i=0; i<n; i++) {
	//	printf("biore:%d\t%d health, cost: %d, diff: %d\n", monsters[i].index, z, monsters[i].cost, monsters[i].diff);
		if ( z > monsters[i].cost) {
			z += monsters[i].diff;
		} else {
			printf("NIE\n");
			return 0;
		}		
	}
	
	printf("TAK\n");
	for (int i=0; i<n; i++) {
		printf("%d ", monsters[i].index);
	}
	printf("\n");
	return 0;
}