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
// Karol Różycki Zadanie Bohater
#include<cstdio>
#include<algorithm>
#include<vector>
#define MAX 100100
using namespace std;

struct pw{
	int a, d, index;
};

bool mfone(pw const & a, pw const & b){
	return a.a < b.a;
}

bool mftwo(pw const & a, pw const & b){
	return b.d < a.d;
}

pw T[MAX];

vector<pw> filtered;
vector<int> output;

int main(){
	int n;
	long long int z;
	bool result = true;
	scanf("%d %lld", &n, &z);
	for(int i = 0; i < n; i++){
		scanf("%d %d", &T[i].a, &T[i].d);
		T[i].index = i;
	}
	sort(T, T + n, mfone);
	for(int i = 0; i < n; i++){
		if(T[i].a - T[i].d <= 0){
			if(z > T[i].a){
				z += T[i].d - T[i].a;
				output.push_back(T[i].index);
			}else{
				result = false;
				break;
			}
		}else{
			filtered.push_back(T[i]);
		}
	}
	sort(filtered.begin(), filtered.end(), mftwo);
	for(unsigned i = 0; i < (unsigned)filtered.size(); i++){
		if(z > filtered[i].a){
			z += filtered[i].d - filtered[i].a;
			output.push_back(filtered[i].index);			
		}else{
			result = false;
			break;
		}
	}
	if(result){
		printf("TAK\n");
		for(unsigned i = 0; i < (unsigned)output.size() - 1; i++){
			printf("%d ", output[i] + 1);
		}
		printf("%d\n", output.back() + 1);
	}else{
		printf("NIE\n");
	}
	filtered.clear();
	output.clear();
	return 0;
}