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

class Run {
public:
	Run(int id, int dmg, int heal) : id(id), dmg(dmg), heal(heal) {}
	int id, dmg, heal;
};

std::vector<Run*> healingRuns;
std::list<Run*> damagingRuns;
std::list<Run*> hardestMonsters;
std::vector<Run*> killingOrder;

int main(int argc, char* argv[]) {
	int monsters, dmg, heal;
	long life, heuro;
	scanf("%d %ld", &monsters, &life);
	heuro = life;

	for(int i = 0; i < monsters; i++) {
		scanf("%d %d", &dmg, &heal);
		heuro += heal - dmg;
		Run* r = new Run(i+1, dmg, heal);
		if(dmg <= heal) {
			if(dmg < life) {
				killingOrder.push_back(r);
				life += heal - dmg;
			} else {
				healingRuns.push_back(r);
			}
		} else {
			damagingRuns.push_back(r);
			hardestMonsters.push_back(r);
		}
	}
	if(heuro <= 0) {
		printf("NIE\n");
		return 0;
	}
	while(healingRuns.size() > 0) {
		bool unableToKillMore = true;
		healingRuns.erase(std::remove_if(healingRuns.begin(), healingRuns.end(), [&](Run* r) {
			if(r->dmg < life) {
				unableToKillMore = false;
				life += heal - dmg;
				killingOrder.push_back(r);
				return true;
			} 
			else return false;
		}), healingRuns.end());
		if(unableToKillMore) {
			printf("NIE\n");
			return 0;
		}
	}

	hardestMonsters.sort([](Run* a, Run* b) {
		return a->dmg < b->dmg;
	});
	
	damagingRuns.sort([](Run* a, Run* b) {
		int aa = a->dmg - a->heal, bb = b->dmg - b->heal;
		return (aa == bb) ? (a->dmg < b->dmg) : (aa > bb);
	});

	while(damagingRuns.size() > 0) {
		Run* d = damagingRuns.back();
		Run* h = hardestMonsters.back();

		if(life <= h->dmg) {
			printf("NIE\n");
			return 0;
		}
		if((life - d->dmg + d->heal) <= h->dmg) {
			for(std::list<Run*>::iterator it = damagingRuns.begin(); it != damagingRuns.end(); it++) {
				Run* r = *it;
				if(r->id == h->id) {
					life += r->heal - r->dmg;
					killingOrder.push_back(r);
					damagingRuns.erase(it);
					break;
				}
			}
			hardestMonsters.pop_back();
		} else if(dmg < life) {		
			for(std::list<Run*>::iterator it = hardestMonsters.begin(); it != hardestMonsters.end(); it++) {
				Run* r = *it;
				if(r->id == d->id) {
					life += r->heal - r->dmg;
					killingOrder.push_back(r);
					hardestMonsters.erase(it);
					break;
				}
			}
			damagingRuns.pop_back();
		} else {
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	for(Run* r : killingOrder) printf("%d ", r->id);
	return 0;
}