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
123
124
125
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct str {
	int num;
	int wej;
	int wyj;	
}pp;

bool comp(pp a, pp b) {
	if (a.wej == b.wej)
		return a.wyj > b.wyj;
	return a.wej < b.wej;
}

bool comp1(pp a, pp b) {
	if (a.wej == b.wej)
		return a.wyj > b.wyj;
	return a.wej > b.wej;
}

void print(vector<int> &wyn) 
{
	vector<int>::iterator it; 
	for(it = wyn.begin(); it != wyn.end(); ++it) {
		cout << *it ;//<< " ";	
	}
	cout<<endl;
}

bool execute(vector<pp> &ujemne, vector<pp> &zero, vector<pp> &dodatnie, vector<pair<int, int> > &a, 	vector<int> &wyn, long long int &start) 
{
	vector<pp>::iterator it;
	vector<pair<int, int> >::iterator it1;
	for(it = dodatnie.begin(); it != dodatnie.end(); ++it) {
		if	(start - it->wej > 0) {
			start -= it->wej;
			start += it->wyj;
			wyn.push_back(it->num);
		} else return false; 
	}
	for(it = zero.begin(); it != zero.end(); ++it) {
		if	(start - it->wej > 0) {
			start -= it->wej;
			start += it->wyj; 
			wyn.push_back(it->num);			
		} else return false; 	
	}
	
	it = ujemne.begin();
	it1 = a.begin();
	bool ok = true;
	while (it1 != a.end()) {
		ok = true;
		if (start - it->wej <= 0) return false;
		if (ujemne[it1->second].wej != -1) {
			if (start - it1->first > it->wej) {
				start	-= it1->first;
				ujemne[it1->second].wej = -1;
				wyn.push_back(ujemne[it1->second].num);
			} else {
				ok = false;
				start -= it->wej;
				start += it->wyj;
				it->wej = -1;
				wyn.push_back(it->num);				
				it++; 			
			}
			while(it != ujemne.end() && it->wej == -1){++it;}	
		}
		if(ok) it1++;
	}
	return true;
}

int main()
{
	cin.sync_with_stdio(false);
	vector<pp> ujemne;
	vector<pp> zero;
	vector<pp> dodatnie;
	vector<int> wyn;
	vector<pair<int, int> > p;
	pp tmp;
	int n, a, b;
	long long int z;	
	cin >> n >> z;
	for (int i = 0; i < n; ++i) {
		cin >> a >> b;
		tmp.num = i+1;
		tmp.wej = a;
		tmp.wyj = b;
		if (b-a > 0) {
			dodatnie.push_back(tmp);		
		} else
		if (b-a < 0) {
			ujemne.push_back(tmp);		
		} else
		if (b-a == 0) {
			zero.push_back(tmp);		
		}
	}
	sort(ujemne.begin(), ujemne.end(), comp1);	
	sort(zero.begin(), zero.end(), comp);	
	sort(dodatnie.begin(), dodatnie.end(), comp);
	
	vector<pp>::iterator it;
	int i =0;
	for(it = ujemne.begin(); it != ujemne.end(); ++it) {
		p.push_back(pair<int, int>(it->wej - it->wyj, i));
		i++;	
	}	
	sort(p.begin(), p.end());
	if (execute(ujemne, zero, dodatnie, p, wyn, z)) {
		cout << "TAK" << endl;
		print(wyn);	
	} else {
print(wyn);	
		cout << "NIE" << endl;	
	}
	return 0;
}