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

using namespace std;

typedef long long int LL;



class Monster {
public:

	Monster() {}

	static Monster load(int number) {
		LL damageVal = 0, potionVal = 0;
		cin >> damageVal;
		cin >> potionVal;
		return Monster(damageVal, potionVal, number);
	}

	static bool compProfitable(const Monster & it, const Monster & that) {
		return it.damage < that.damage;
	}

	static bool compNotProfitable(const Monster & it, const Monster & that) {
		return it.lowest(that) < that.lowest(it);
	}

	LL lowest(const Monster & that) const {
		return max(damage, damage - potion + that.damage);
	}

	bool isProfitable() {
		return potion > damage;
	}

	int beDefeated(LL health) {
		if(health <= damage)
			return 0;
		else
			return health - damage + potion;
	}

	int getNumber() {
		return number;
	}

private:
	Monster(LL damageVal, LL potionVal, int num) {
		damage = damageVal;
		potion = potionVal;
		number = num;
	}

	LL damage;
	LL potion;
	int number;
};


LL defeatMonster(LL currentHealth, Monster monsterToDefeat) {
	return monsterToDefeat.beDefeated(currentHealth);
}

bool isProfitable(Monster monster) {
	return monster.isProfitable();
}

int main() {
	ios_base::sync_with_stdio(0);
	int monstersCount = 0;
	LL initHealth = 0;
	cin >> monstersCount >> initHealth;
	vector<Monster> monsters(monstersCount);
	for(int i = 0; i < monstersCount; ++i) {
		monsters[i] = Monster::load(i+1);
	}

	auto separatingIterator = partition(monsters.begin(), monsters.end(), ptr_fun(isProfitable));
	sort(monsters.begin(), separatingIterator, Monster::compProfitable);
	sort(separatingIterator, monsters.end(), Monster::compNotProfitable);
	LL finalHealth = accumulate(monsters.begin(), monsters.end(), initHealth, defeatMonster);

	if(finalHealth <= 0) {
		cout << "NIE\n";
	} else {
		cout << "TAK\n";
		for(Monster defeatedMonster: monsters)
			cout << defeatedMonster.getNumber() << " ";
		cout << endl;
	}


}