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
#include<stdlib.h>
#include<stdio.h>

#define MAX 100000

struct ad {
	int a;
	int d;
	int i;
};

int compare (const void * a, const void * b)
{
	struct ad* a1 = (struct ad*)a;
	struct ad* b1 = (struct ad*)b;
	
	//printf(" a = %d    d = %d\n", a1->a, a1->d);
	
	// sortujemy malejaco wg a
	return ( b1->a - a1->a );
	
	// stare:
	// sortujemy rosnaco wg ujemnych zyskow
	// a1->d - a1->a  = koszt - przychód = ujemny zysk
	//if ( a1->d - a1->a < b1->d - b1->a ) return -1;
	//if ( a1->d - a1->a > b1->d - b1->a ) return 1;
	
	// w przypadku rownosci zyskow
	// pierwszy ma byc ten z mniejszym kosztem
	//if ( a1->d - a1->a == b1->d - b1->a ) return ( a1->d - b1->d );
}

int main(int argc, char ** argv) {

	int n, z, i, ord_i, to_kill, nothing_killed;
	struct ad ads[MAX];
	char killed[MAX];
	int order[MAX];
	
	// wczytanie
	scanf("%d %d\n", &n, &z);
	for(i = 0; i < n; i++) {
		scanf("%d %d\n", &(ads[i].d), &(ads[i].a));
		ads[i].i = i + 1;
	}
	
	// sortowanie
	qsort (ads, n, sizeof(struct ad), compare);
	
	//for(i = 0; i < n; i++) {
	//	printf("%d %d\n", ads[i].d, ads[i].a);
	//}
	
	ord_i = 0;
	nothing_killed = 0;
	to_kill = n;
	while (to_kill > 0 && !nothing_killed) {
		i = 0;
		nothing_killed = 1;
		while (nothing_killed && i < n) {
			if (killed[i]) i++;
			else if (ads[i].d >= z) i++;
			else {
				killed[i] = 1;
				to_kill--;
				z += ads[i].a - ads[i].d;
				nothing_killed = 0;
				order[ord_i] = ads[i].i;
				ord_i++;
				//printf("[%d] killing, damage: %d  addition: %d\n", i + 1,  ads[i].d, ads[i].a);
				//printf("\t now pz: %d\n", z);
			}
		}
	}
	if (nothing_killed) {
		printf("NIE");
	}
	else {
		printf("TAK\n");
		for(i = 0; i < n; i++) {
			printf("%d ", order[i]);
		}
	}
	
	return 0;
}