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
#include <cstdio>
#include <vector>
#include <queue>
#include <utility>

static const unsigned int MAX_MONSTERS_COUNT = 100 * 1000;
static const unsigned int MAX_HP = 100 * 1000;

struct Monster
{
	int id;
	int hpDrain, hpReward;
	
	inline int hpDelta() const
	{
		return hpReward - hpDrain;
	}
	
	struct OutcomeCompare
	{
		inline bool operator()(const Monster & m1, const Monster & m2) const
		{
			return m1.hpDelta() < m2.hpDelta();
		}
	};
	
	struct MinHPCompare
	{
		inline bool operator()(const Monster & m1, const Monster & m2) const
		{
			return m1.hpDrain > m2.hpDrain;
		}
	};
};

typedef std::priority_queue<Monster, std::vector<Monster>, Monster::OutcomeCompare> deltaQueue_t;
typedef std::priority_queue<Monster, std::vector<Monster>, Monster::MinHPCompare> drainQueue_t;

bool solve(
	long long hp,
	drainQueue_t & monstersTooHardToKill,
	std::vector<int> & killingOrder
)
{
	deltaQueue_t candidatesForMove;
	int monsterCount = monstersTooHardToKill.size();
	
	for (int i = 0; i < monsterCount; i++)
	{
		while (!monstersTooHardToKill.empty()
			&& hp - monstersTooHardToKill.top().hpDrain > 0)
		{
			candidatesForMove.push(monstersTooHardToKill.top());
			monstersTooHardToKill.pop();
		}
		
		if (candidatesForMove.empty())
			return false;
		
		killingOrder.push_back(candidatesForMove.top().id);
		hp += candidatesForMove.top().hpDelta();
		candidatesForMove.pop();
	}
	
	return true;
}

int main()
{
	int monsterCount;
	long long hp, endHp;
	scanf("%d %lld", &monsterCount, &hp);
	endHp = hp;
	
	drainQueue_t positiveMonsters, negativeMonsters;
	std::vector<int> positiveKillingOrder, negativeKillingOrder;
	
	for (int i = 0; i < monsterCount; i++)
	{
		Monster m;
		m.id = i + 1;
		scanf("%d %d", &m.hpDrain, &m.hpReward);
		
		endHp += m.hpDelta();
		
		if (m.hpDelta() >= 0)
			positiveMonsters.push(m);
		else
		{
			std::swap(m.hpDrain, m.hpReward);
			negativeMonsters.push(m);
		}
	}
	
	if (endHp > 0 &&
		solve(hp,    positiveMonsters, positiveKillingOrder) &&
		solve(endHp, negativeMonsters, negativeKillingOrder))
	{
		puts("TAK");
		
		for (auto it = positiveKillingOrder.begin(); it != positiveKillingOrder.end(); it++)
			printf("%d ", *it);
		
		for (auto it = negativeKillingOrder.rbegin(); it != negativeKillingOrder.rend(); it++)
			printf("%d ", *it);
		
		puts("");
	}
	else
		puts("NIE");
	
	return 0;
}