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
118
119
120
121
122
123
124
#include <iostream>
#include <algorithm>

using namespace std;

struct monster
{
	long int hit;
	long int potion;
	long int index;

	bool operator <(const monster& a) const
	{
		if ( hit < a.hit )
		{
			return false;
		}
		else if ( hit == a.hit )
		{
			return potion < a.potion;
		}

		return true;
	}

	bool operator >(const monster& a) const
	{
		return !((*this) < a);
	}
};

monster positive[100001];
monster negative[100001];
long int positive_max = 0;
long int negative_max = 0;
long long int diff = 0;

void pput(long int value)
{
	static bool first = true;

	if ( !first )
	{
		cout << " " << value;
		return;
	}

	cout << value;
	first = false;
}

int main()
{
	long int monserCount;
	long int health;
	long int healthLost;
	long long int healthGain;
	cin >> monserCount >> health;

	for( long int monserIndex = 0; monserIndex < monserCount; ++monserIndex )
	{
		cin >> healthLost >> healthGain;

		if ( healthLost < healthGain )
		{
			positive[positive_max].hit = healthLost;
			positive[positive_max].potion = healthGain;
			positive[positive_max++].index = monserIndex;
		}
		else
		{
			negative[negative_max].hit = healthLost;
			negative[negative_max].potion = healthGain;
			negative[negative_max++].index = monserIndex;
		}

		diff = diff + healthGain - healthLost;
	}

	if ( diff <= health )
	{
		sort(positive, positive + positive_max, greater < monster >());
		sort(negative, negative + negative_max, less < monster >());

		for ( int i = 0; i < positive_max; ++i )
		{
			if ( positive[i].hit >= health )
			{
				cout << "NIE" << endl;
				return 0;
			}
			health = health - positive[i].hit + positive[i].potion;
		}

		for ( int i = 0; i < negative_max; ++i )
		{
			if ( negative[i].hit >= health )
			{
				cout << "NIE" << endl;
				return 0;
			}
			health = health - negative[i].hit + negative[i].potion;
		}
		cout << "TAK" << endl;

		for ( int i = 0; i < positive_max; ++i )
		{
			pput(positive[i].index+1);
		}

		for ( int i = 0; i < negative_max; ++i )
		{
			pput(negative[i].index+1);
		}

		cout << endl;
	}
	else
	{
		cout << "NIE" << endl;
	}

	return 0;
}