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
#define NDEBUG
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
#define TRACE(x) cerr<<"# "#x<<endl;
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<endl;
typedef unsigned long long ULL;
typedef long long LL;
const int INF = 0x7FFFFFFF;

struct P {
	int d, b, i;

	P(int d, int b, int i):d(d), b(b), i(i) {}
};

int main() {

	int n, z;
	LL life;
	vector<P> v1, v2;

	scanf("%d %d", &n, &z);

	v1.reserve(n+2);
	v2.reserve(n+2);

	for(int i=0; i<n ;++i) {
		int d, a, b;
		scanf("%d %d", &d, &a);
		b = a - d;
		if(b >= 0) {
			v1.push_back(P(d,b,i));
		} else {
			v2.push_back(P(d,b,i));
		}
	}

	sort(v1.begin(), v1.end(), [](const P &a, const P &b) -> bool {return a.d < b.d;});
	sort(v2.begin(), v2.end(), [](const P &a, const P &b) -> bool {return a.d > b.d;});

	life = z;

	for(const P &p : v1) {
		if(life > p.d) {
			life += p.b;
		} else {
			life = 0ll;
			break;
		}
	}

	for(const P &p : v2) {
		if(life > p.d) {
			life += p.b;
		} else {
			life = 0ll;
			break;
		}
	}

	if(life > 0ll) {
		printf("TAK\n");
		for(const P &p : v1) { printf("%d ", p.i+1); }
		for(const P &p : v2) { printf("%d ", p.i+1); }
	} else {
		printf("NIE");
	}
	printf("\n");

	return 0;
}