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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int max_monsters = 100 * 1000;

typedef struct monster {
	int dmg;
	int elx;
	int num;
	monster(int d, int e, int n) :
			dmg(d), elx(e), num(n) {
	}
} monster_t;

bool less_dmg(const struct monster& a, const struct monster& b) {
	return a.dmg < b.dmg;
}

bool greater_elx(const struct monster& a, const struct monster& b) {
	return a.elx > b.elx;
}

bool check(int hero_hp, const vector<monster>& better_monsters, const vector<monster>& worse_monsters) {
	bool answer = true;

	for (unsigned i = 0; i < better_monsters.size(); ++i) {
		if (hero_hp > better_monsters[i].dmg) {
			hero_hp += better_monsters[i].elx - better_monsters[i].dmg;
		} else {
			return false;
		}

	}

	for (unsigned i = 0; i < worse_monsters.size(); ++i) {
		if (hero_hp > worse_monsters[i].dmg) {
			hero_hp += worse_monsters[i].elx - worse_monsters[i].dmg;
		} else {
			return false;
		}

	}

	return answer;
}

void solve() {
	int monster_count;
	int hero_hp;
	vector<monster> better_monsters;
	vector<monster> worse_monsters;
	int monster_dmg;
	int monster_elx;

	cin >> monster_count >> hero_hp;

	better_monsters.reserve(monster_count);
	worse_monsters.reserve(monster_count);

	for (int i = 0; i < monster_count; ++i) {
		cin >> monster_dmg >> monster_elx;
		if (monster_elx >= monster_dmg) {
			better_monsters.push_back(monster_t(monster_dmg, monster_elx, i + 1));
		} else {
			worse_monsters.push_back(monster_t(monster_dmg, monster_elx, i + 1));
		}
	}

	sort(better_monsters.begin(), better_monsters.end(), less_dmg);
	sort(worse_monsters.begin(), worse_monsters.end(), greater_elx);

	if (check(hero_hp, better_monsters, worse_monsters)) {
		cout << "TAK" << endl;
		for (unsigned i = 0; i < better_monsters.size(); ++i) {
			cout << better_monsters[i].num << " ";
		}
		for (unsigned i = 0; i < worse_monsters.size(); ++i) {
			cout << worse_monsters[i].num << " ";
		}
		cout << endl;

	} else {
		cout << "NIE" << endl;
	}
}

int main() {
	ios_base::sync_with_stdio(0);

	solve();

	return 0;
}