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
// boh.cpp : Defines the entry point for the console application.
//



#include "stdio.h"
#include "stdlib.h"

#define	NN	100000

struct	ppp	{
				int		 d;
				int		 a;
				int		 s;
			}	 pp[NN+1];

int				 ii[NN+1];

int				 i, k, n, z, a, d;
int				 debug = 0;
long long		 s;


int
compii(const void *x, const void *y)
{
	int		 ix, iy, s, r;

	ix	= *((int *) x);
	iy	= *((int *) y);
	s	= pp[ix].s;
	r	= pp[iy].s - s;
	if (r==0)
	{
		if (s>0)
			r	= pp[ix].d - pp[iy].d;
		else
			r	= pp[iy].a - pp[ix].a;
	}

	return r;
}

void
boh()
{
	scanf("%d%d", &n, &z);
	for (i=1; i<=n; i++)
	{
		ii[i]	= i;
		scanf("%d%d", &d, &a);
		pp[i].d	= d;
		pp[i].a	= a;
		a	-= d;
		if (a)
			a	= (a<0) ? -1 : 1;

		pp[i].s	= a;
	}

	qsort(ii+1, n, sizeof(int), compii);

	if (debug)
		for (i=1; i<=n; i++)
		{
			k	= ii[i];
			printf("%d -> %d %d\n", k, pp[k].d, pp[k].a);
		}

	s	= z;
	for (i=1; i<=n; i++)
	{
		k	= ii[i];
		s	-=	pp[k].d;
		if (s<=0)
			n	= 0;

		s	+= pp[k].a;
	}

	printf("%s\n", n==0 ? "NIE" : "TAK");
	for (i=1; i<=n; i++)
		printf("%d ", ii[i]);

	printf("\n");
}

int
main()
{
	boh();

	return 0;
}