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

using namespace std;

typedef long long LL;

const int MaxN = 100001;

int N, Z;
struct Monster {
	int damage, antidotum, num;
	
	Monster(int d=0, int a=0, int i=0) : damage(d), antidotum(a), num(i) {}
	
	bool operator<(const Monster &M) const {
		// operator do sortowania do zachlana
		bool incrThis = (damage <= antidotum),
		     incrM = (M.damage <= M.antidotum);
		
		// zawsze najpierw oplaca sie brac te potwory, po ktorych
		// HP rosnie
		if(incrThis ^ incrM){
			return incrThis;
		}
		
		// jak ostatecznie HP rosnie, to warto najpierw brac te
		// opcje, gdzie jest mniejszy damage
		if(incrThis){
			return damage < M.damage;
		} else {
			// a jak maleje, to najpierw te, gdzie miksturki sa lepsze
			return antidotum > M.antidotum;
		}
	}
};
Monster M[MaxN];

void input(){
	scanf("%d%d", &N, &Z);
	
	for(int i = 0; i < N; i++){
		int d, a;
		scanf("%d%d", &d, &a);
		M[i] = Monster(d, a, i+1);
	}
}

bool can_kill(LL HP){
	for(int i = 0; i < N; i++){
		HP -= M[i].damage;
		if(HP <= 0) return false;
		
		HP += M[i].antidotum;
	}
	return true;
}


void output(bool result){
	if(result){
		printf("TAK\n");
		for(int i = 0; i < N; i++)
			printf("%d ", M[i].num);
		printf("\n");
	} else {
		printf("NIE\n");
	}
}


int main(){
	input();
	sort(M, M+N);
	
	// przetwarzamy
	output(can_kill(Z));
}