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

enum {
	MAX = 100010
};

int dmg[MAX];
int heal[MAX];
int tab1[MAX];
int tab2[MAX];
int neg = 0;

bool comp1(int a, int b)
{
	if(dmg[a] == dmg[b])
		return heal[a] > heal[b];
	return dmg[a] < dmg[b];
}

bool comp2(int a, int b)
{
	if(heal[a] == heal[b])
		return dmg[a] < dmg[b];
	return heal[a] > heal[b];
}

int main()
{
	int n, _z; scanf("%d%d", &n, &_z);
	long long z = _z;
	for(int i = 0; i < n; i++)
	{
		scanf("%d%d", dmg+i, heal+i);
		if(heal[i] >= dmg[i])
			tab1[i-neg] = i;
		else
			tab2[neg++] = i;
	}
	std::sort(tab1, tab1+n-neg, comp1);
	std::sort(tab2, tab2+neg, comp2);
	bool res = 1;
	for(int i = 0; i < n-neg && res; i++)
	{
		z -= dmg[tab1[i]];
		if(z <= 0) {res = 0; break; }
		z += heal[tab1[i]];
	}
	for(int i = 0; i < neg && res; i++)
	{
		z -= dmg[tab2[i]];
		if(z <= 0) {res = 0; break; }
		z += heal[tab2[i]];
	}
	if(res)
	{
		printf("TAK\n");
		for(int i = 0; i < n-neg; i++)
			printf("%d ", tab1[i]+1);
		for(int i = 0; i < neg; i++)
			printf("%d ", tab2[i]+1);
		printf("\n");
	}
	else
		printf("NIE\n");
	return 0;
}