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

#define getchar_custom getc_unlocked

char c;

template <typename T>
inline T read_custom() {

	c = getchar_custom(stdin);

	while (c<'0' || c>'9')
	{
		c = getchar_custom(stdin);
	}

	T returnValue = 0;
	while (c >= '0' && c <= '9') {
		returnValue = (returnValue << 3) + (returnValue << 1) + c - 48;
		c = getchar_custom(stdin);
	}

	return returnValue;
}

struct monster {
	int position;
	int attack;
	int bonus_att_diff;
};

struct monsterCmp {
	bool operator()(monster const *a, monster const *b) {
		return a->attack < b->attack;
	};
};

int main() {
	int monstersNo = read_custom<int>();
	long long life = read_custom<long long>();

	std::vector<monster*> monsters;
	std::vector<int> max_diff;

	for (int i = 1; i <= monstersNo; i++) {
		monster *m = new monster;
		m->position = i;
		m->attack = read_custom<int>();
		m->bonus_att_diff = read_custom<int>() - m->attack;

		monsters.push_back(m);
	}

	std::make_heap(monsters.begin(), monsters.end(), monsterCmp());
	std::sort_heap(monsters.begin(), monsters.end(), monsterCmp());

	std::deque<monster*> battle;

	while (monsters.size() > 0) {

		int pos = 0;
		while (pos < monsters.size() && monsters[pos]->attack < life && monsters[pos]->bonus_att_diff < 0) {
			pos += 1;
		}

		if (pos == monsters.size() && (monsters[pos-1]->attack >= life)) {
			std::cout << "NIE" << std::endl;
			return 0;
		}
		else if (pos == monsters.size())
		{
			pos -= 1;
		}

		if (monsters[pos]->bonus_att_diff >= 0) {

			if (monsters[pos]->attack == life) {
				std::cout << "NIE" << std::endl;
				return 0;
			}

			life += monsters[pos]->bonus_att_diff;
			battle.push_back(monsters[pos]);
			monsters.erase(monsters.begin() + pos);

			continue;
		}

		if (monsters[pos]->attack >= life)
		{
			std::cout << "NIE" << std::endl;
			return 0;
		}

		life += monsters[pos]->bonus_att_diff;
		battle.push_back(monsters[pos]);
		monsters.erase(monsters.begin() + pos);
	}

	if (life <= 0) {
		std::cout << "NIE" << std::endl;
		return 0;
	}

	std::cout << "TAK" << std::endl;

	while (battle.size() > 0) {
		monster *tmp = battle.front();
		battle.pop_front();
		std::cout << tmp->position;

		if (battle.size() > 0) {
			std::cout << " ";
		}
	}
}