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
/*
 * Potyczki Algorytmiczne 2014
 * Round 2 - division B (aka Quest for a cool t-shirt)
 *
 * Author: Mateusz (jam231) Jany 
 */

#include <iostream>
#include <vector>
#include <algorithm>

#include <stdint.h>

using namespace std;

static const int cin_buffer_size = 1024 * 8;
static char cin_buffer[cin_buffer_size] = {0};
static const int cout_buffer_size = 1024 * 8;
static char cout_buffer[cout_buffer_size] = {0};

struct monster_data {
	int32_t i; 
	int32_t d; 
	int32_t a;
};

bool d_i_asc(const monster_data& a, const monster_data& b)
{
	return a.d < b.d;
}

bool d_i_desc(const monster_data& a, const monster_data& b)
{
	return a.d > b.d;
}

/*
 * So... forall k. z_k > d_i[k+1] 
 *
 */

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.rdbuf()->pubsetbuf(cin_buffer, cin_buffer_size);
	std::cout.rdbuf()->pubsetbuf(cout_buffer, cout_buffer_size);
	int32_t n, z;
	int32_t a_i, d_i;

	cin >> n >> z;

	vector<monster_data> life_gaining, life_losing;
	// The code below is "one ugly bastard" ;-(
	for(int i = 0; i < n; i++)
	{
		cin >> d_i >> a_i;

		if (a_i >= d_i)
		{
			life_gaining.push_back({i + 1, d_i, a_i});
		}
		else
		{
			life_losing.push_back({i + 1, d_i, a_i});
		}
	}

	sort(life_gaining.begin(), life_gaining.end(), d_i_asc);
	sort(life_losing.begin(), life_losing.end(), d_i_desc);

	for(int i = 0; i < life_gaining.size(); i++)
	{
		if(z <= life_gaining[i].d)
		{
			cout << "NIE\n";
			return 0;
		}
		else
		{
			z += (life_gaining[i].a - life_gaining[i].d);
		}
	}

	for(int i = 0; i < life_losing.size(); i++)
	{
		if(z <= life_losing[i].d)
		{
			cout << "NIE\n";
			return 0;
		}
		else
		{
			z += (life_losing[i].a - life_losing[i].d);
		}
	}

	if(z > 0)
	{
		cout << "TAK\n";
		for(int i = 0; i < life_gaining.size(); i++)
		{
			cout << life_gaining[i].i << " ";		
		}
		for(int i = 0; i < life_losing.size(); i++)
		{
			cout << life_losing[i].i << " ";		
		}
	}
	else
	{
		cout << "NIE\n";
	}
	return 0;
}