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

int main() {
	int N;
	long long int Z;
	long long int X=0;
	std::vector<int> result, result2;
	std::vector<std::pair<int, std::pair<int,int> > > good, bad;

	scanf("%d %lld",&N,&Z);
	for (int i=0; i<N; ++i) {
		int rem,add;
		scanf("%d %d",&rem,&add);

		if (add>=rem) {
			good.push_back(std::make_pair(rem,std::make_pair(add, i+1)));
		} else {
			X += add - rem;
			bad.push_back(std::make_pair(add, std::make_pair(rem,i+1)));
		}
	}

	std::sort(good.begin(), good.end());
	for (int i=0; i<good.size(); ++i) {
		if (Z > good[i].first) {
			result.push_back(good[i].second.second);
			Z = Z + good[i].second.first - good[i].first;
		} else {
			printf("NIE\n");
			return 0;
		}
	}

	X += Z;
	std::sort(bad.begin(), bad.end());
	for (int i=0; i<bad.size(); ++i) {
		if (X > bad[i].first) {
			result2.push_back(bad[i].second.second);
			X += bad[i].second.first - bad[i].first;
		} else {
			printf("NIE\n");
			return 0;
		}
	}

	printf("TAK\n");
	for (int i=0; i<result.size(); ++i) printf("%d ",result[i]);
	if (result2.size()>0) { for (int i=result2.size()-1; i>=0; --i) printf("%d ",result2[i]); }

	return 0;
}