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
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <iostream>
#include <math.h>
#include <set>
#include <algorithm>
#include <vector>
#include <string.h>
#define For(i, n) for (int i = 0; i < (n); i++)
#define ForD(i, n) for (int i = (n) - 1; i >= 0; i--)
#define in cin>>
#define out cout<<
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
using namespace std;
typedef long long LL;

struct monster
{
	int attack, life;
	int index;

	monster(bool _read = false)
	{
		attack = life = 0;
		if (_read)
			read();
	}

	inline void	read()
	{
		in attack >> life;
	}
};

const int N = 1e5 + 1;
bool cmpPositive(monster lhs, monster rhs)
{
	if (lhs.attack != rhs.attack)
		return lhs.attack < rhs.attack;
	return lhs.life > rhs.life;
}

bool cmpNegative(monster lhs, monster rhs)
{
	if (lhs.life != rhs.life)
		return lhs.life > rhs.life;
	return lhs.attack > rhs.attack;
}

int main()
{
	ios_base::sync_with_stdio();
	int Life, n;
	in n >> Life;
	
	vector<monster> Positive, Negative;
	
	For (i, n)
	{
		monster m(true);
		if (m.life >= m.attack)
			Positive.push_back(m),
			Positive.back().index = i + 1;
		else
			Negative.push_back(m),
			Negative.back().index = i + 1;
	}

	sort(Positive.begin(), Positive.end(), cmpPositive);

	bool Possible = true;
	For(i, Positive.size())
	{
		if (Life <= Positive[i].attack)
		{
			Possible = false;
			break;
		}
		else
			Life += Positive[i].life - Positive[i].attack;
	}

	if (!Possible)
	{
		out "NIE\n";
		return 0;
	}

	sort(Negative.begin(), Negative.end(), cmpNegative);
	For(i, Negative.size())
	{
		if (Life <= Negative[i].attack || Life <= 0) 
		{
			Possible = false;
			break;
		}

		Life += Negative[i].life - Negative[i].attack;
	}
	if (Life <= 0)
		Possible = false;

	if (!Possible)
		out "NIE\n";
	else
	{
		out "TAK\n";
		For(i, Positive.size())
			out Positive[i].index << " ";
		For(i, Negative.size())
			out Negative[i].index << " ";
	}
	
	//system("pause");
	return 0;
}