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
//Łukasz Proksa, Silesian University of Technology, Poland
//Contest:	Potyczki Algorytmiczne 2014
//Round:	2
//Task:		Bohater [B]
//Solved!	O(n*log n)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define FOR(i, p, k) for(int i = (p); i < (k); i++)
#define SCAST static_cast

typedef long long LL;

const int MAX_N = 100001; //100tys potworow

struct potwor {
	int d, a, s, id; //damage, add, suma, id potwora
	bool used;
};

int n, trasa[MAX_N];
vector <potwor> pluss, minuss;
LL z;

bool cmpP(potwor a, potwor b) {
	if(a.d < b.d) return true;
	else if(a.d == b.d) {
		if(a.s > b.s) return true;
	}
	return false;
}

bool cmpM(potwor a, potwor b) {
	if(a.a > b.a) return true;
	else if(a.a == b.a) {
		if(a.d > b.d) return true;
	}
	return false;
}

int main() {
	scanf("%d %lld", &n, &z);
	FOR(i, 0, n) {
		potwor godzilla;
		scanf("%d %d", &godzilla.d, &godzilla.a);
		godzilla.s = godzilla.a - godzilla.d; //ile doda do zycia bohatera
		godzilla.id = i+1;
		godzilla.used = false;
		if(godzilla.s >= 0) {
			pluss.push_back(godzilla);
		}else {
			minuss.push_back(godzilla);
		}
	}
	sort(pluss.begin(), pluss.end(), cmpP);
	sort(minuss.begin(), minuss.end(), cmpM);
	
	int i;
	int sizeP = pluss.size();
	FOR(i, 0, sizeP) { ////////dodatnie
		if(z - pluss[i].d <= 0) {
			printf("NIE\n");
			return 0;
		}
		z += SCAST<LL>(pluss[i].s);
		trasa[i] = pluss[i].id;
	}
	int sizeM = minuss.size();
	FOR(i, 0, sizeM) {   //////////////ujemne
		if(z - minuss[i].d <= 0) {
			printf("NIE\n");
			return 0;
		}
		z += SCAST<LL>(minuss[i].s);
		trasa[sizeP+i] = minuss[i].id;
	}
	
	printf("TAK\n");
	FOR(i, 0, n) {
		printf("%d ", trasa[i]);
	}
	printf("\n");
	return 0;
}