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
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>	
using namespace std;

bool sortPositive(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
	return a.first.first < b.first.first;
}

bool sortNegative(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
	return a.first.second > b.first.second;
}

int main(){
	int n, z;
	scanf("%d",&n);
	scanf("%d",&z);
	
	vector<int> l;

	vector<pair<pair<int, int>, int> > positive;
	vector<pair<pair<int, int>, int> > negative;

	int d, p;
	for (int i=0 ; i<n ; i++){
		scanf("%d",&d);
		scanf("%d",&p);
		if ((p-d)>=0){
			positive.push_back(make_pair(make_pair(d, p), i+1));
		}else{
			negative.push_back(make_pair(make_pair(d, p), i+1));
		}
	}

	sort(positive.begin(), positive.end(), sortPositive);
	sort(negative.begin(), negative.end(), sortNegative);

	for (int i=0 ; i<positive.size() ; i++){
		z -= positive[i].first.first;
		if (z<1) {
			printf("NIE\n");
			return 0;
		}
		z += positive[i].first.second;
		l.push_back(positive[i].second);
	}

	for (int i=0 ; i<negative.size() ; i++){
		z -= negative[i].first.first;
		if (z<1) {
			printf("NIE\n");
			return 0;
		}
		z += negative[i].first.second;
		l.push_back(negative[i].second);
	}

	printf("TAK\n");
	for (int i=0 ; i<l.size() ; i++) printf("%d ", l[i]);
	printf("\n");
	return 0;
}