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
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include<iostream>
#include<list>
#include<vector>


using namespace std;

typedef vector<int> prow;
typedef vector<prow> ptable;
typedef list<prow> plist;


int t(prow& pi) {
	return pi[1] - pi[0];
}

int d(prow& pi) {
	return pi[0];
}

int a(prow& pi) {
	return pi[1];
}

int idx(prow& pi) {
	return pi[2];
}

void partition(ptable& p, plist& t_plus, plist& t_minus) {
	for(int i = 0; i < p.size(); i++) {
		int ti = t(p[i]);
		if(ti >= 0) {
			t_plus.push_front(p[i]);
		} else {
			t_minus.push_front(p[i]);
		}
	}
}

bool maxT(prow r1, prow r2) {
	return t(r1) > t(r2);
}

bool maxDA(prow r1, prow r2) {
	int d1 = r1[0];
	int d2 = r2[0];
	return (d1 != d2) ? d1 > d2 : r1[1] > r2[1];
}

bool canWin(plist& t_plus, plist& t_minus, int z, vector<int>& path) {
	long sum = z;
	int pcnt = 0;

	for(auto it = t_plus.begin(); it != t_plus.end(); it++) {
		int di = d(*it);
		if(di < sum) {
			path[pcnt++] = idx(*it);
			sum += t(*it);
			t_plus.erase(it);
			it = t_plus.begin();
		}
	}
	if(!t_plus.empty()) {
		return false;
	}


	for(auto it = t_minus.begin(); it != t_minus.end(); it++) {
		int di = d(*it);
		if(di >= sum) {
			return false;
		} else {
			path[pcnt++] = idx(*it);
			sum += t(*it);
		}
	}

	return true;
}

void print_path(vector<int>& path) {
	string sep = "";
	for(auto it = path.begin(); it != path.end(); it++) {
		cout << sep << (*it + 1);
		sep = " ";
	}
	cout << endl;
}


int main() {
	int n, z;
	cin >> n >> z;

	plist t_plus;
	plist t_minus;
	{
		ptable p(n);

		for(int i = 0; i < n; i++) {
			p[i].resize(3);
			int d, a;
			cin >> d >> a;
			p[i][0] = d;
			p[i][1] = a;
			p[i][2] = i;
		}

		partition(p, t_plus, t_minus);
	}

	t_plus.sort(maxT);
	t_minus.sort(maxDA);

	vector<int> path(n);

	bool can = canWin(t_plus, t_minus, z, path);
	cout << (can ? "TAK" : "NIE") << endl;
	if(can) {
		print_path(path);
	}
}