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
#include <bits/stdc++.h>
//#include <emmintrin.h>

using namespace std;

#define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define FOR(i,a,b)  for(int i=(a);i<(b);++i)
#define REP(i,a)    FOR(i,0,a)
#define ZERO(m)    memset(m,0,sizeof(m))
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define S          size()
#define LL          long long
#define ULL        unsigned long long
#define LD          long double
#define MP          make_pair
#define X          first
#define Y          second
#define VC          vector
#define PII        pair <int, int>
#define VI          VC < int >
#define VVI        VC < VI >
#define VD          VC < double >
#define VVD        VC < VD >
#define VS          VC < string >
#define DB(a)      cerr << #a << ": " << (a) << endl;

template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}

const int MAXN = 101000;
int n;
LL h;
int d[MAXN];
int a[MAXN];
int rv[MAXN];
PII p0[MAXN];
PII p1[MAXN];
int main() {
	cin >> n >> h;
	REP(i, n) scanf("%d%d",d+i,a+i);
	LL oh = h;
	
	int s0 = 0, s1 = 0;
	REP(i, n) {
		if (d[i] <= a[i]) {
			p0[s0++] = MP(d[i], i);
		} else {
			p1[s1++] = MP(a[i], i);
		}
	}
	sort(p0, p0 + s0);
	sort(p1, p1 + s1);
	
	assert(s0 + s1 == n);
	
	bool ok = true;
	REP(i, s0) {
		int p = p0[i].Y;
		ok &= h > d[p];
		h += a[p] - d[p];
		rv[i] = p;
	}
	REP(i, s1) {
		int p = p1[i].Y;
		h += a[p] - d[p];
	}
	REP(i, s1) {
		int p = p1[i].Y;
		ok &= h - a[p] > 0;
		h -= a[p] - d[p];
		rv[n - 1 - i] = p;
	}
	
	if (ok) {
		cout << "TAK" << endl;
		REP(i, n) cout << (rv[i]+1) << ' ';
		cout << endl;
	} else {
		cout << "NIE" << endl;
	}
	return 0;
}