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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct potwor
{
	int d;
	int a;
	int orig_idx;
	potwor(int d_, int a_, int i_) : d(d_), a(a_), orig_idx(i_) { } ;
};

typedef vector<potwor> vp;
typedef vector<int> vi;

bool compare_d(const potwor &A, const potwor &B)
{
	return A.d < B.d;
}

bool compare_a_d(const potwor &A, const potwor &B)
{
	return A.a > B.a  ||  A.a == B.a && A.d > B.d;
}

void check_curr_health(const vp &v, long long &curr, vi &res)
{
	for(vp::const_iterator d = v.begin() ; d != v.end() ; d++)
	{
		curr -= d->d;
		if(curr <= 0)
		{
			printf("NIE\n");
			exit(0);
		}
		curr += d->a;
		res.push_back(d->orig_idx);
	}
}

int main(int argc, char* argv[])
{
#ifdef DO_REDIRECT
	freopen("BOH.dat", "rt", stdin);
	freopen("BOH.sol", "wt", stdout);
#endif
	int N;
	int start;
	scanf("%d %d", &N, &start);
	vp dodatne, ujemne;
	dodatne.reserve(N);
	ujemne.reserve(N);
	for(int i=0; i<N; i++)
	{
		int d, a;
		scanf("%d %d", &d, &a);
		if(d<=a)
			dodatne.push_back(potwor(d,a,i+1));
		else
			ujemne.push_back(potwor(d,a,i+1));
	}
	sort(dodatne.begin(), dodatne.end(), compare_d);
	sort(ujemne.begin(), ujemne.end(), compare_a_d);
	long long curr = start;
	vi res(0);
	check_curr_health(dodatne, curr, res);
	check_curr_health(ujemne, curr, res);
	printf("TAK\n%d", res[0]);
	for(int i=1; i<N; i++)
		printf(" %d", res[i]);
	printf("\n");
	return 0;
}