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 <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int MAXN = 100005;
long long lifeLevel;
int monstersNumber;

struct monster
{
	int healthNeed;
	int treatment;
	int number;
};
vector< monster > feed; 
vector< monster > hit;

int lastConsidered = 1;

bool sortCmpHealth(const monster & a, const monster &b)
{
	if(a.healthNeed != b.healthNeed)
		return a.healthNeed < b.healthNeed;
	return a.number < b.number;
}
bool sortCmpTreatment(const monster & a, const monster &b)
{
	if(a.treatment != b.treatment)
		return a.treatment > b.treatment;
	if(a.healthNeed != b.healthNeed)
		return a.healthNeed < b.healthNeed;
		
	return a.number < b.number;
}


int result[MAXN];
int lastAdded = 1;

void get()
{
	scanf("%d %llu", &monstersNumber, &lifeLevel);
	//printf("%d %llu", monstersNumber, lifeLevel);
	monster temp;
	for(int i = 1; i <= monstersNumber; ++i){
		temp.number = i;
		scanf("%d %d", &temp.healthNeed, &temp.treatment);
		//printf("%d %d\n", temp.healthNeed, temp.treatment);
		if(temp.healthNeed <= temp.treatment)
			feed.push_back(temp);
		else
			hit.push_back(temp);
	}
}

bool perform()
{
	sort(feed.begin(), feed.end(), sortCmpHealth);
	sort(hit.begin(), hit.end(), sortCmpTreatment);
	for(vector<monster>::iterator it = feed.begin(); it != feed.end(); ++it){
		if((*it).healthNeed >= lifeLevel)
			return false;
		lifeLevel += (*it).treatment - (*it).healthNeed;
		result[lastAdded++] = (*it).number;
	}
	for(vector<monster>::iterator it = hit.begin(); it != hit.end(); ++it){
		if((*it).healthNeed >= lifeLevel)
			return false;
		lifeLevel += (*it).treatment - (*it).healthNeed;
		result[lastAdded++] = (*it).number;
	}
	return true;
}

int main()
{
	get();
	if(perform()){
		printf("TAK\n");
		for(int i = 1; i < lastAdded; ++i)
			printf("%d ", result[i]);
	}else{
		printf("NIE\n");
	}
}