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
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) __typeof(n) x = (n)
#define FOREACH(x,n) for(VAR(x,(n).begin());x!=(n).end();++x)

int n, d,a;
long long z;

struct PII {
	int first;
	int second;
	int third;
	PII(int f, int s, int t): first(f), second(s), third(t) {}
	PII() {}
};

struct comp1 {
	bool operator() (const PII& e, const PII& f) {
		return e.first==f.first ? e.third < f.third : e.first < f.first;
	}
};
struct comp2 {
	bool operator() (const PII& e, const PII& f) {
		return e.first+e.second == f.first+f.second ? e.third<f.third : e.first+e.second > f.first+f.second;
	}
};

set<PII, comp1> plusy;
set<PII, comp2> minusy;

int main() {
	ios_base::sync_with_stdio(false);
	cin>>n>>z;
	vector<int> odp;
	odp.reserve(n);
	set<PII>::iterator it;
	long long suma_minusy=0; ///minusy od wrogów
	REP(x,n) {
		cin>>d>>a;
		if (d>a) {/// więcej straci niż zyska po walce
			minusy.insert(PII(d,a-d,x));
			suma_minusy += d-a;
		} else if (d>=z) /// zginie
			plusy.insert(PII(d,a-d,x));
		else {
			odp.push_back(x);
			z += a-d;
			while(plusy.size() && (it=plusy.begin())->first < z) {
				odp.push_back(it->third);
				z += it->second;
				plusy.erase(it);
			}
		}
	}
	if (plusy.size() || z<=suma_minusy) {
		cout << "NIE" << endl;
		return 0;
	}
	FOREACH(it, minusy) {
		if (z<=it->first) {
			cout << "NIE" << endl;
			return 0;
		}
		z += it->second;
		odp.push_back(it->third);
	}
	cout << "TAK " << endl;
	FOREACH(it, odp)
		cout << *it+1 << " ";
//	FOREACH(it, minusy)
//		cout << "("<<it->first<<","<<it->second<<","<<it->third+1<<") ";
	return 0;
}