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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public final class boh {
	private static final String SEPARATOR = "\\s+";
	private static final String RESULT_SEPARATOR = " ";

	public static InputStream INPUT_STREAM = System.in;
	public static PrintStream PRINT_STREAM = System.out;

	private static List<Integer> result;
	private static int life;

	private static final class Monster {
		Integer id;
		int demage;
		int health;
		int gain;

		public Monster(final int id, final int demage, final int health) {
			this.id = id;
			this.demage = demage;
			this.health = health;
			gain = health - demage;
		}

		@Override
		public String toString() {
			return String.format("%s [demage=%s, health=%s, gain=%s]", id, demage, health, gain);
		}

	}

	private static final Comparator<Monster> lowestDamageComparator = new Comparator<boh.Monster>() {
		@Override
		public int compare(Monster a, Monster b) {
			return -(b.demage - a.demage);
		}
	};

	private static final Comparator<Monster> highestDamageComparator = new Comparator<boh.Monster>() {
		@Override
		public int compare(Monster a, Monster b) {
			return b.demage - a.demage;
		}
	};

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(INPUT_STREAM));

		String[] tmp = br.readLine().split(SEPARATOR);

		int monstersNumber = Integer.parseInt(tmp[0]);
		life = Integer.parseInt(tmp[1]);
		result = new ArrayList<Integer>(monstersNumber);

		List<Monster> easy = new LinkedList<Monster>();
		List<Monster> hard = new LinkedList<Monster>();

		for (int i = 0; i < monstersNumber; i++) {
			tmp = br.readLine().split(SEPARATOR);
			Monster monster = new Monster(i + 1, Integer.parseInt(tmp[0]), Integer.parseInt(tmp[1]));

			if (monster.gain >= 0) {
				easy.add(monster);
			} else {
				hard.add(monster);
			}
		}

		boolean yes = solve(easy, hard);

		PRINT_STREAM.println(yes ? "TAK" : "NIE");

		if (yes) {
			StringBuilder builder = new StringBuilder();

			for (Integer id : result) {
				builder.append(id).append(RESULT_SEPARATOR);

			}
			PRINT_STREAM.println(builder.substring(0, builder.length() - 1));
		}

	}

	private static boolean solve(List<Monster> easy, List<Monster> hard) {
		Collections.sort(easy, lowestDamageComparator);

		if (defeat(easy)) {
			Collections.sort(hard, highestDamageComparator);

			return defeat(hard);
		}

		return false;

	}

	private static boolean defeat(List<Monster> monsters) {
		for (Monster monster : monsters) {
			if (monster.demage >= life) {
				return false;
			}

			life += monster.gain;
			result.add(monster.id);

		}

		return true;
	}

}