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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Monster{
public:
	int damage;
	int heal;
	int number;
};

bool compareInc(Monster x, Monster y) {
	return x.damage < y.damage;
}

bool compareDec(Monster x, Monster y) {
	return x.damage > y.damage;
}

int main() {

	int n;
	int life;

	cin >> n >> life;

	vector<Monster> monstersInc;
	vector<Monster> monstersDec;

	monstersInc.reserve(n);
	monstersDec.reserve(n);

	vector<int> order;

	Monster temp;

	for (int i = 0; i < n; ++i){

		cin >> temp.damage >> temp.heal;

		if (temp.damage > temp.heal){
			temp.number = i + 1;
			monstersDec.push_back(temp);
		} else {
			if (life > temp.damage){
				life += temp.heal - temp.damage;
				order.push_back(i + 1);
			} else {
				temp.number = i + 1;
				monstersInc.push_back(temp);
			}
		}

	}

	sort(monstersInc.begin(), monstersInc.end(), compareInc);
	sort(monstersDec.begin(), monstersDec.end(), compareDec);

	bool impossible = false;

	//cout << "rosnace\n";
	for (int i = 0; i < monstersInc.size() && !impossible; ++i){
		//cout << "damage = " << monstersInc[i].damage << " heal = " << monstersInc[i].heal << endl;
		if (monstersInc[i].damage < life){
			life += monstersInc[i].heal - monstersInc[i].damage;
			order.push_back(monstersInc[i].number);
		} else {
			//cout << "impossible\n";
			impossible = true;
		}
		//cout << "life = " << life << endl;
	}
	//cout << "malejace\n";
	for (int i = 0; i < monstersDec.size() && !impossible; ++i){
		//cout << "damage = " << monstersDec[i].damage << " heal = " << monstersDec[i].heal << endl;
		if (monstersDec[i].damage < life){
			life += monstersDec[i].heal - monstersDec[i].damage;
			order.push_back(monstersDec[i].number);
		} else {
			//cout << "impossible\n";
			impossible = true;
		}
		//cout << "life = " << life << endl;
	}

	if (impossible){
		cout << "NIE\n";
	} else {
		cout << "TAK\n";
		for (int i = 0; i < order.size(); ++i){
			cout << order[i] << " ";
		}
		cout << endl;
	}

	return 0;

}