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

const int MAXN = 100005;
int n,z,d[MAXN],a[MAXN],order[MAXN];
std::vector<int> positiveBalance,negativeBalance;

void init();
bool damageComp(int,int);
bool healthComp(int,int);

int main()
{
	init();
	scanf("%d%d", &n, &z);
	for(int i = 0; i < n; ++i)
		scanf("%d%d", &d[i], &a[i]);
	
	for(int i = 0; i < n; ++i)
		if(a[i] - d[i] < 0)
			negativeBalance.push_back(i);
		else positiveBalance.push_back(i);
	
	std::sort(positiveBalance.begin(), positiveBalance.end(), damageComp);
	std::sort(negativeBalance.begin(), negativeBalance.end(), healthComp);

	int currHealth = z;
	for(int i = 0; i < positiveBalance.size(); ++i)
	{
		currHealth -= d[positiveBalance[i]];
		if(currHealth <= 0)
			{ printf("NIE\n"); return 0; }
		currHealth += a[positiveBalance[i]];
	}
	for(int i = 0; i < negativeBalance.size(); ++i)
	{
		currHealth -= d[negativeBalance[i]];
		if(currHealth <= 0)
			{ printf("NIE\n"); return 0; }
		currHealth += a[negativeBalance[i]];
	}

	printf("TAK\n");
	for(int i = 0; i < positiveBalance.size(); ++i)
		printf("%d ", positiveBalance[i]+1);
	for(int i = 0; i < negativeBalance.size(); ++i)
		printf("%d ", negativeBalance[i]+1);
	printf("\n");
}

void init()
{
	for(int i = 0; i < MAXN; ++i)
		order[i] = i;
}

bool damageComp(int x, int y)
{
	return d[x] < d[y];
}

bool healthComp(int x, int y)
{
	return a[x] > a[y];
}