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

struct mons {
	int d;
	int a;
	int inc;
	int i;
};

const int N_MAX = 100000;

bool print_NIE_and_quit() {
	cout << "NIE" << endl;
	exit(0);
}

int main() {
	int n;
	long long z;
	cin >> n >> z;
	
	mons m_pos[N_MAX], m_neg[N_MAX];
	int pos_c = 0;
	int neg_c = 0;
	int d, a, inc;
	mons m;
	for (int i=0; i<n; i++) {
		cin >> d >> a;
		inc = a - d;
		
		m.d = d;
		m.a = a;
		m.inc = inc;
		m.i = i + 1;
		if (inc >= 0) {
			m_pos[pos_c++] = m;
		} else {
			m_neg[neg_c++] = m;
		}
	}
	
	sort(m_pos, m_pos + pos_c,
		[](const mons & a, const mons & b) -> bool
		{ 
		    return a.d < b.d;
	});
	
	sort(m_neg, m_neg + neg_c,
		[](const mons & a, const mons & b) -> bool
		{ 
			if (a.inc != b.inc)
			    return a.inc < b.inc;
			else
				return a.d > b.d;
	});
	
	for (int i=0; i < pos_c; i++) {
		z -= m_pos[i].d;
		if (z <= 0)
			print_NIE_and_quit();
		z += m_pos[i].a;
	}
	
	for (int i=0; i < neg_c; i++) {
		z -= m_neg[i].d;
		if (z <= 0)
			print_NIE_and_quit();
		z += m_neg[i].a;
	}
	
	cout << "TAK" << "\n";
	for (int i=0; i < pos_c; i++) {
		cout << m_pos[i].i << " ";
	}
	for (int i=0; i < neg_c; i++) {
		cout << m_neg[i].i << " ";
	}
	cout << endl;
	
	return 0;
}