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
95
96
97
#include "cstdio"
#include "algorithm"
using namespace std;
long long n,k,a,b,p,m,z,wyn[100005],w;
pair <pair<long long,long long>, pair<long long,long long> > plusy[100005],zera[100005],minusy[100005];
bool ok;
int main()
{
	scanf ("%lld%lld", &n, &k);
	for (int i=0; i<n; i++)
	{
		scanf ("%lld%lld", &a, &b);
		if (a<b)
		{
			plusy[p].first.first=a;
			plusy[p].first.second=(b-a)*(-1);
			plusy[p].second.first=b;
			plusy[p].second.second=i+1;
			p++;
		}
		else if (a>b)
		{
			minusy[m].first.first=b*(-1);
			minusy[m].second.first=a;
			minusy[m].second.second=i+1;
			m++;
		}
		else
		{
			zera[z].first.first=a;
			zera[z].first.second=(b-a)*(-1);
			zera[z].second.first=b;
			zera[z].second.second=i+1;
			z++;
		}
	}
	sort (plusy, plusy+p);
	sort (zera, zera+z);
	sort (minusy, minusy+m);
  

	ok=true;
	for (int i=0; i<p; i++)
	{		
		k-=plusy[i].first.first;
		if (k<=0)
		{
			ok=false;
			break;
		}
		k+=plusy[i].second.first;
		wyn[w]=plusy[i].second.second;
		w++;
	}
  
	if (k>0)
	{
		for (int i=0; i<z; i++)
		{
			k-=zera[i].first.first;
			if (k<=0)
			{
				ok=false;
				break;
			}
			k+=zera[i].second.first;
			wyn[w]=zera[i].second.second;
			w++;
		}
	}
  
	if (k>0)
	{
		for (int i=0; i<m; i++)
		{
			k-=minusy[i].second.first;
			if (k<=0)
			{
				ok=false;
				break;
			}
			k+=(minusy[i].first.first*(-1));
			wyn[w]=minusy[i].second.second;
			w++;
		}
	}
  
	if (!ok) printf ("NIE\n");
	else
	{
		printf ("TAK\n");
		for (int i=0; i<w; i++) printf ("%lld ", wyn[i]);
	}
    
	
	return 0;
}