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

using namespace std;

class Monster
{

private:

	int attack_power;
	int healing_potion;
	int number;

public:

	Monster(int attack_power, int healing_potion, int number)
	{
		this->attack_power = attack_power;
		this->healing_potion = healing_potion;
		this->number = number + 1;
	}

	int hit() const
	{
		return attack_power;
	}

	int receive_healing_potion() const
	{
		return this->healing_potion;
	}

	int get_number() const
	{
		return this->number;
	}

	int get_difference() const
	{
		return this->healing_potion - this->attack_power;
	}
	
};

struct CompareMonsters
{
	bool operator()(const Monster &lhs, const Monster &rhs)
	{
		if(lhs.get_difference() <= 0 && rhs.get_difference() <= 0)
			return lhs.receive_healing_potion() < rhs.receive_healing_potion();
		else if(lhs.get_difference() > 0 && rhs.get_difference() > 0)
			return lhs.hit() > rhs.hit();
		else
			return lhs.get_difference() < rhs.get_difference();
	}
};

int main()
{
	int health, n;
	int healing_potion, damage;
	queue<int> fight_order;
	scanf("%d %d", &n, &health);
	priority_queue<Monster, vector<Monster>, CompareMonsters> monsters;
	for(int i = 0; i < n; ++i)
	{
		scanf("%d %d", &damage, &healing_potion);
		monsters.push(*(new Monster(damage, healing_potion, i)));
	}
	while(!monsters.empty())
	{
		health -= monsters.top().hit();
		if(health <= 0)
			break;
		health += monsters.top().receive_healing_potion();
		fight_order.push(monsters.top().get_number());
		monsters.pop();
	}
	if(health <= 0)
		printf("NIE\n");
	else
	{
		printf("TAK\n");
		while(!fight_order.empty())
		{
			printf("%d ", fight_order.front());
			fight_order.pop();
		}
	}
	return 0;
}