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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;

class Monster
{
public:
	int diff;
	int dmg;
	int potion;
	int id;

	Monster(int id, int d, int h) : diff(h - d), dmg(d), potion(h), id(id) {}
	friend ostream& operator<<(ostream &os, const Monster &m);
};

ostream& operator<<(ostream &os, const Monster &m){
	return os << "id = " << m.id << ", dmg = " << m.dmg << ", potion = " << m.potion << ", delta = " << m.diff;
}

// maks diff
// inline bool operator<(const Monster &a, const Monster &b){
// 	if(a.diff > b.diff){
// 		return true;
// 	}
// 	else if(a.diff == b.diff && (a.potion > b.potion)){
// 		return true;
// 	}
// 	return false;
// }

// maks potiony
inline bool operator<(const Monster &a, const Monster &b){
	if(a.potion > b.potion){
		return true;
	}
	else if(a.potion == b.potion && (a.diff > b.diff)){
		return true;
	}
	return false;
}


// inline bool monsterSort(const Monster &a, const Monster &b){
// 	return (a.diff > b.diff) || (a.potion > b.potion);
// }

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


	int no_monsters = 0;
	int c_health = 0;
	cin >> no_monsters >> c_health;
	long long int nie_test = c_health;

	vector<Monster > mons;
	vector<Monster > mons_0potion;
	vector<int > mons_path;

	mons.reserve(no_monsters);
	mons_0potion.reserve(no_monsters/2);
	mons_path.reserve(no_monsters);

	for (int i = 1; i <= no_monsters; i++)
	{
		int d,h;
		cin >> d >> h;
		nie_test -= d;
		nie_test += h;
		if(h > 0){
			mons.push_back(Monster(i, d, h));
		}
		else{
			mons_0potion.push_back(Monster(i, d, h));
		}
	}

	// impossible
	if(nie_test <= 0){
		cout << "NIE" << endl;
		return 0;
	}

	sort(mons.begin(), mons.end());

	// append 0 potion monsters
	move(mons_0potion.begin(), mons_0potion.end(), inserter(mons, mons.end()));
	// sort(mons.begin(), mons.end(), monsterSort);


#ifdef DEBUG
	int round = 1;
#endif

	while(mons.size() > 0){
#ifdef DEBUG
		cout << "Round " << round++ << " Health: " << c_health << endl;
		for(const auto &x : mons){
			cout << "  " << x << endl;
		}
#endif
		auto r = find_if(mons.begin(), mons.end(), [& c_health](const Monster &m){ return m.dmg < c_health; });
#ifdef DEBUG
		cout << "    find_if: " << *r << endl;
#endif

		// cant find beatable monster
		if(r == mons.end() && mons.size() > 0){
			cout << "NIE" << endl;
			return 0;
		}

		// found beatable monster
		// if( r != mons.end()){
		mons_path.push_back( (*r).id );
		c_health -= (*r).dmg;
		// i am dead
		if(c_health <= 0){
			cout << "NIE" << endl;
			return 0;
		}
		c_health += (*r).potion;
		mons.erase(r);
		// }
		// else{
		// 	cout << "r == mons.end()!" << endl;
		// }
	}
	cout << "TAK" << endl;
	for(const auto &x : mons_path){
		cout << x << " ";
	}
	cout << endl;

	return 0;
}