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

using namespace std;

class Monster{
	int monsterNo;
	int damage;
	int potion;
public:
	Monster(int i, int d, int a):monsterNo(i), damage(d), potion(a){}
	int monsterFactor()const{
		return potion - damage;
	}
	int getMonsterNo()const{return monsterNo;}
	int getDamage()const{return damage;}
	int getPotion()const{return potion;}
	friend bool operator <(Monster, Monster);
	friend ostream& operator<< (ostream&, Monster const&);
};

bool operator < (Monster a, Monster b){
    //return a.monsterFactor() > b.monsterFactor();
    return a.getDamage() < b.getDamage();
}

ostream& operator<< (ostream &out, Monster const& m){
	out << "Monster number: " << m.getMonsterNo() << endl;
	out << "Damage: " << m.getDamage() << endl;
	out << "Potion: " << m.getPotion() << endl;
	out << "Monster factor: " << m.monsterFactor() << endl;
	return out;
}

bool potionSort(Monster a, Monster b){
	return a.getPotion() > b.getPotion();
}

int main(){
	ios_base::sync_with_stdio(0);
	int monsterCount, lifeTotal;
	int d, a;
	vector<Monster> goodMonsters;
	vector<Monster> badMonsters;
	vector<int> order;
	cin >> monsterCount;
	cin >> lifeTotal;
	for(int i=1; i<= monsterCount; i++){
		cin >> d;
		cin >> a;
		if(a >= d){
			goodMonsters.push_back(Monster(i, d, a));
		}
		else{
			badMonsters.push_back(Monster(i, d, a));
		}
	}
	sort(goodMonsters.begin(), goodMonsters.end());
	sort(badMonsters.begin(), badMonsters.end(), potionSort);
  	//reverse(badMonsters.begin(), badMonsters.end());

	/*for (int i=0; i<goodMonsters.size();i++){
    	cout << goodMonsters[i];
  	}
  	for (int i=0; i<badMonsters.size();i++){
    	cout << badMonsters[i];
  	}*/

  	bool possible = true;
  	for(int i=0;i<goodMonsters.size();i++){
  		if(goodMonsters[i].getDamage() < lifeTotal){
  			lifeTotal += goodMonsters[i].monsterFactor();
  			order.push_back(goodMonsters[i].getMonsterNo());
  		}
  		else{
  			possible = false;
  			break;
		}
  	}
  	if(possible){
  		for(int i=0;i<badMonsters.size();i++){
  			if(badMonsters[i].getDamage() < lifeTotal){
	  			lifeTotal += badMonsters[i].monsterFactor();
	  			order.push_back(badMonsters[i].getMonsterNo());
	  		}
	  		else{
	  			possible = false;
	  			break;
			}
		}
  	}
  	if(possible){
  		cout << "TAK\n";
  		//reverse(order.begin(), order.end());
  		for(int i=0;i<order.size();i++){
  			cout << order[i] << " ";
  		}
  		cout << endl;
  	}
  	else
  		cout << "NIE\n";
}