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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct monster {
	int id, damage, hp;
};

inline bool highFilter (monster * a, monster * b) {
	if( a->damage < b->damage || ( a->damage == b->damage && a->hp > b->hp ))
		return true;
	return false;
}

inline bool lowFilter (monster * a, monster * b) {
	if( a->hp > b->hp || ( a->hp == b->hp && a->damage < b->damage ))
		return true;
	return false;
}

int main() {

	int N, HP, i, diff;
	scanf("%d %d", &N, &HP);

	long possibility = HP;

	vector< monster * > highMonsters;
	vector< monster * > zeroMonsters;
	vector< monster * > lowMonsters;
	monster * m;

	for(i = 1; i <= N; ++i) {
		m = new monster;
		m->id = i;
		scanf("%d %d", &m->damage, &m->hp);
		diff = m->hp - m->damage;
		possibility += diff;
		if(diff < 0)
			lowMonsters.push_back(m);
		else if(diff == 0)
			zeroMonsters.push_back(m);
		else
			highMonsters.push_back(m);
	}

	if(possibility <= 0) {
		puts("NIE");
		return(0);
	}

	sort(highMonsters.begin(), highMonsters.end(), highFilter);
	sort(lowMonsters.begin(), lowMonsters.end(), lowFilter);

	long life = HP;

	for (monster* m : highMonsters) {
		life -= m->damage;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
		life += m->hp;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
	}
	for (monster* m : zeroMonsters) {
		life -= m->damage;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
		life += m->hp;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
	}
	for (monster* m : lowMonsters) {
		life -= m->damage;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
		life += m->hp;
		if(life < 1) {
			puts("NIE");
			return(0);
		}
	}
	puts("TAK");

	for (monster* m : highMonsters) {
		printf("%d ", m->id);
		delete m;
	}
	for (monster* m : zeroMonsters) {
		printf("%d ", m->id);
		delete m;
	}
	for (monster* m : lowMonsters) {
		printf("%d ", m->id);
		delete m;
	}
	puts("");

	return(0);
}