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

using namespace std;

struct Monster {
	int index;
	int damage;
	int potion;
};

bool comparePotion(Monster a, Monster b) {
	return a.potion < b.potion;
}

bool compareDamage(Monster a, Monster b) {
	return a.damage < b.damage;
}

int main()
{
	ios::sync_with_stdio(0);
	
	int n;
	unsigned long long z;
	
	cin >> n >> z;
	
	vector<Monster> gain;
	vector<Monster> pain;
	
	vector<int> pathPlus;
	vector<int> pathMinus;
	
	long long finalLife = z;
	
	for(int i = 0 ; i < n; i++) {
			Monster monster;
			monster.index = i+1;
			cin >> monster.damage >> monster.potion;
			finalLife -= (monster.damage - monster.potion);
			if(monster.damage <= monster.potion) {
				gain.push_back(monster);
			} else {
				pain.push_back(monster);
			}
	}
	
	if(finalLife < 1) {
		cout << "NIE" << endl;
		return 0;
	}
	
	sort(gain.begin(), gain.end(), compareDamage);
	sort(pain.begin(), pain.end(), comparePotion);
	
	for(unsigned int i = 0; i < gain.size(); i++) {
		if(gain[i].damage < z) {
			z = z + (gain[i].potion - gain[i].damage);
			pathPlus.push_back(gain[i].index);
		} else {
			cout << "NIE" << endl;
			return 0;
		}
	}
	
	for(unsigned int i = 0; i < pain.size(); i++) {
		if(pain[i].potion < finalLife) {
			finalLife = finalLife + (pain[i].damage - pain[i].potion);
			pathMinus.push_back(pain[i].index);
		} else {
			cout << "NIE" << endl;
			return 0;
		}
	}
	
	cout << "TAK" << endl;
	
	for(unsigned int i = 0 ; i < pathPlus.size(); i++) cout << pathPlus[i] << " ";
	for(unsigned int i = 0; i < pathMinus.size(); i++) cout << pathMinus[pathMinus.size()-i-1] << " ";
	
	cout << endl;
	
	return 0;
}