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
// Piotr Golda
#define _CRT_SECURE_NO_WARNINGS  
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
using namespace std;
#define LLD long long int
#define MAX_NUM 100000

int N;
LLD V;
pair<int,int> T[ MAX_NUM ];
vector< int > Profitable;
vector< int > Unprofitable;


bool cmp(int p_lhs, int p_rhs)
{ return  T[p_lhs] < T[p_rhs]; }

bool cmp2(int p_lhs, int p_rhs)
{ 
	return   T[p_lhs].second  > T[p_rhs].second;
}

void scan()
{
	scanf("%d %lld", &N, &V);

	for(int i = 0; i < N; ++i)
	{
		scanf("%d %d", &T[i].first, &T[i].second);
		if( T[i].second >= T[i].first)
			Profitable.push_back( i );
		else
			Unprofitable.push_back( i );
	}
}

bool ComputeAndCheckPath()
{
	sort( Profitable.begin(), Profitable.end(), cmp );
	sort( Unprofitable.begin(), Unprofitable.end(), cmp2 );

	for( int i = 0; i < Profitable.size(); ++i )
	{
		if( V - (LLD)T[ Profitable[i] ].first <= 0 )
			return false;
		V += (LLD)T[ Profitable[i] ].second - (LLD)T[ Profitable[i] ].first;
	}

	for( int i = 0; i < Unprofitable.size(); ++i )
	{
		if( V - (LLD)T[ Unprofitable[i] ].first <= 0 )
			return false;
		V += (LLD)T[ Unprofitable[i] ].second - (LLD)T[ Unprofitable[i] ].first;
	}
	return true;
}

void printPath()
{
	for( int i = 0; i < Profitable.size(); ++i )
	{
		printf("%d ", Profitable[i] + 1);
	}

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



int main()
{
	scan();
	if( ComputeAndCheckPath() )
	{
		printf("TAK\n");
		printPath();
	}
	else
		printf("NIE\n");
	return 0;
}