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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <limits>
#include <iostream>
#include <cassert>
#include <tuple>

// POCZATEK szybkiego wczytywania

#define INPUT_BUFFER_SIZE 100000

inline char my_getchar()
{
	static char _input_buffer[INPUT_BUFFER_SIZE + 1];
	static int _buffer_pos = INPUT_BUFFER_SIZE;

	if (_buffer_pos == INPUT_BUFFER_SIZE) {
		int t = std::fread(_input_buffer, 1, INPUT_BUFFER_SIZE, stdin);
		_input_buffer[t] = EOF;
		_buffer_pos = 0;
	}
	return _input_buffer[_buffer_pos++];
}

inline void read_int(int &n)
{
	char c;
	bool read = false;
	n = 0;
	while (true) {
		c = my_getchar();
		if ('0' <= c && c <= '9') {
			read = true;
			n = 10 * n + c - '0';
		}
		else if (read || c == EOF) {
			break;
		}
	}
}
// KONIEC szybkiego wczytywania

int main()
{
	int n, health;

	std::ios_base::sync_with_stdio(false);

	read_int(n);
	read_int(health);

	std::vector<std::tuple<int, int, int>> gain;
	std::vector<std::tuple<int, int, int>> lose; // first - damage, second - potion, third - index

	std::vector<int> sequence;

	for (int i = 1; i <= n; i++) {
		int damage, potion;

		read_int(damage); // damage
		read_int(potion); // potion

		if (potion >= damage)
			gain.push_back(std::make_tuple(damage, potion, i));
		else
			lose.push_back(std::make_tuple(potion, damage, i));
	}

	std::sort(gain.begin(), gain.end());
	std::sort(lose.begin(), lose.end());// , std::greater<std::tuple<int, int, int>>());

	for (int i = 0; i < static_cast<int>(gain.size()); i++) {
		if (std::get<0>(gain[i]) < health) {
			health -= std::get<0>(gain[i]);
			health += std::get<1>(gain[i]);
			sequence.push_back(std::get<2>(gain[i]));
		}
		else {
			std::printf("NIE\n");
			return 0;
		}
	}

	int health_backwards = 1; // we need to have at least 1 point of health at finish
	std::vector<int> sequence_backwards;

	for (int i = 0; i < static_cast<int>(lose.size()); i++) {
		if (std::get<0>(lose[i]) >= health_backwards)
			health_backwards = std::get<0>(lose[i]) + 1;

		//assert(std::get<0>(lose[i]) < health_backwards);

		health_backwards -= std::get<0>(lose[i]);
		health_backwards += std::get<1>(lose[i]);
		sequence_backwards.push_back(std::get<2>(lose[i]));
	}

	if (health_backwards > health) {
		std::printf("NIE\n");
		return 0;
	}

	for (int i = sequence_backwards.size() - 1; i >= 0; i--)
		sequence.push_back(sequence_backwards[i]);

	std::printf("TAK\n");

	for (int i = 0; i < n; i++)
		std::printf("%d ", sequence[i]);
	std::printf("\n");
}