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
#include <iostream>
#include <sstream>
using namespace std;

struct Monster {
	int d,a,p,profit;
	double uprofit;
};

int get_the_best_index(Monster* monsters, int z, int n) {
	int best_index = -1;
	double max_uprofit;
	for(int i = 0; i < n; i++){
		if(monsters[i].d < z && 
			(best_index == -1 ||
			monsters[i].uprofit > max_uprofit || 
			(monsters[i].uprofit == max_uprofit && monsters[i].d > monsters[best_index].d) ||
			(monsters[i].uprofit == max_uprofit && monsters[i].d == monsters[best_index].d && monsters[i].profit > monsters[best_index].profit))){
			best_index = i;
			max_uprofit = monsters[i].uprofit;
		}
	}
	return best_index;
}

void swap(Monster* monsters, int first, int second){
	Monster tmp = monsters[first];
	monsters[first] = monsters[second];
	monsters[second] = tmp;
}

int main() {
	unsigned int n,z;
	Monster* monsters;
	ostringstream result;
	cin >> n;
	cin >> z;
	monsters = new Monster[n];
	for(unsigned int i = 0; i < n; i++){
		cin >> monsters[i].d;
		cin >> monsters[i].a;
		monsters[i].p = i+1;
		monsters[i].profit = monsters[i].a - monsters[i].d;
		if(monsters[i].d > 0){
			monsters[i].uprofit = (double)monsters[i].a / (double)monsters[i].d;
		} else {
			monsters[i].uprofit = (double)monsters[i].a;
		}
		
	}
	int best_index;
	int i = 0;
	do{
		best_index = get_the_best_index(monsters, z, n);
		if(best_index > -1){
			z += monsters[best_index].profit;
			result << monsters[best_index].p << " ";
			swap(monsters, best_index, n-1);
		} else {
			cout << "NIE" << endl;
			break;
		}
		i++;
	}while(--n);
	if(n == 0){
		cout << "TAK" << endl << result.str() << endl;
	}
	return 0;
}