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
/*
 *  Copyright (C) 2014  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */

#include <tuple>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Monster {
public:
	int damage;
	int heal;
	int index;

	Monster(int d, int h, int i): damage(d), heal(h), index(i) {}

	bool operator<(const Monster& other) const {
		int diff = heal - damage;
		int diff_other = other.heal - other.damage;

		// fight with this will increase health, but fight with other will not
		if (diff >= 0 && diff_other < 0) {
			return true;
		}
		// fight with other will increase health, but fight with this will not
		if (diff_other >= 0 && diff < 0) {
			return false;
		}

		int cost = damage - other.damage;

		// both fights will increase health
		if (diff >= 0 && diff_other >= 0) {
			if (diff > 0 and diff_other == 0) {
				return true;
			}
			if (diff == 0 and diff_other > 0) {
				return false;
			}
			return cost < 0;
		}

		int benefit = heal - other.heal;

		// both fights will decrease health
		if (cost == benefit) {
			return damage > other.damage;
		}
		return cost >= diff_other - diff;
	}
};

int main() {
	unsigned int n;
	unsigned long long health;

	int damage, heal;
	vector<int> fights;
	vector<Monster> monsters;

	ios::sync_with_stdio (false);
	cin >> n >> health;

	for (unsigned int i = 0; i < n; ++i) {
		cin >> damage >> heal;
		monsters.push_back(Monster(damage, heal, i));
	}

	// sort monsters by the cost/benefit difference
	sort(begin(monsters), end(monsters));

	for (auto monster : monsters) {

//cout << "d h i  " << monster.damage << " " << monster.heal << " " << monster.index << endl;

		if (health > (unsigned int) monster.damage) {
			health += monster.heal - monster.damage;
			fights.push_back(monster.index);

//cout << "H  " << health << endl;
		}
	}

	if (fights.size() == n) {
		cout << "TAK" << endl;
		for (auto fight : fights) {
			cout << fight + 1 << " ";
		}
		cout << endl;
	} else {
		cout << "NIE" << endl;
	}

	return 0;
}