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
87
88
89
90
91
92
93
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;

struct Node{
	LL loss;
	LL profit;
	int realIdx;
	
	bool operator<(const Node& other) const{
		return loss < other.loss;
	}
};

vector<Node> posVect, negVect;
vector<int> results;
vector<int> backResults;
int n;

int main(){
	int z, d, a;
	LL life;
	
	scanf("%d%d", &n, &z);
	life = z;
	
	for(int i=0; i<n; i++){
		scanf("%d%d", &d, &a);
		
		Node node;
		node.realIdx = i + 1;
		
		if(a - d >= 0){
			node.loss = d;
			node.profit = a;
			posVect.push_back(node);
		}else{
			node.loss = a;
			node.profit = d;
			negVect.push_back(node);
		}
	}
	
	sort(posVect.begin(), posVect.end());
	sort(negVect.begin(), negVect.end());
	
	for(int i=0; i<(int)posVect.size(); i++){
		Node &node = posVect[i];
		
		if(node.loss >= life){
			printf("NIE\n");
			return 0;
		}
		
		life += node.profit - node.loss;
		results.push_back(node.realIdx);
	}
	
	LL endLife = life;
	
	for(int i=0; i<(int)negVect.size(); i++)
		endLife += negVect[i].loss - negVect[i].profit;
	
	if(endLife <= 0){
		printf("NIE\n");
		return 0;
	}
	
	for(int i=0; i<(int)negVect.size(); i++){
		Node &node = negVect[i];
		
		if(node.loss >= endLife){
			printf("NIE\n");
			return 0;
		}
		
		endLife += node.profit - node.loss;
		backResults.push_back(node.realIdx);
	}
	
	printf("TAK\n");
		
	for(int i=0; i<(int)results.size(); i++)
		printf("%d ", results[i]);
		
	for(int i=(int)backResults.size()-1; i>=0; i--)
		printf("%d ", backResults[i]);
	
	return 0;
}