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

using namespace std;

#define MAXN 100000

typedef struct {
	int nr;
	long long int trudnosc;
	long long int eliksir;
} Potwor;

bool compareLatwe(Potwor i, Potwor j) {
	return i.trudnosc < j.trudnosc;
}

bool comareTrudne(Potwor i, Potwor j) { // true jeśli i < j
	if (i.eliksir == j.eliksir) {
		return i.trudnosc > j.trudnosc;
	} else {
		return i.eliksir > j.eliksir;
	}
}

int odp[MAXN];

int main() {
	int n;

	long long int z;

	Potwor potwory[MAXN];
	Potwor latwe[MAXN];
	Potwor trudne[MAXN];

	int lat = 0;
	int tru = 0;

	bool can = true;

	scanf("%d %lld", &n, &z);

	for (int i = 0; i < n; i++) {
		potwory[i].nr = i + 1;
		scanf("%lld %lld", &potwory[i].trudnosc, &potwory[i].eliksir);

		if (potwory[i].trudnosc <= potwory[i].eliksir) {
			latwe[lat++] = potwory[i];
		} else {
			trudne[tru++] = potwory[i];
		}
	}

	sort(latwe, latwe+lat, compareLatwe);
	sort(trudne, trudne+tru, comareTrudne);

	for (int i = 0; i < lat; i++) {
		if (z > latwe[i].trudnosc) {
			z = z - latwe[i].trudnosc + latwe[i].eliksir;
			odp[i] = latwe[i].nr;
		} else {
			can = false;
			break;
		}
	}

	if (can) {
		for (int i = 0; i < tru; i++) {
			if (z > trudne[i].trudnosc) {
				z = z - trudne[i].trudnosc + trudne[i].eliksir;
				odp[i + lat] = trudne[i].nr;
			} else {
				can = false;
				break;
			}
		}
	}

	if (can) {
		printf("TAK\n");
		for (int i = 0; i < n; i++) {
			printf("%d ", odp[i]);
		}

	} else {
		printf("NIE\n");
	}

	return 0;
}