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
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class boh {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		Set<Dragon> easyDragons = new TreeSet<Dragon>();
		Set<Dragon> hardDragons = new TreeSet<Dragon>(Collections.reverseOrder());
		List<Integer> order = new LinkedList<Integer>();

		int dragons = scanner.nextInt();
		int hp = scanner.nextInt();

		for (int i = 1; i <= dragons; i++) {
			int damage = scanner.nextInt();
			int heal = scanner.nextInt();
			Dragon d = new Dragon(i, damage, heal);

			if (d.isEasy()) {
				easyDragons.add(d);
			} else {
				hardDragons.add(d);
			}
		}

		for (Dragon d : easyDragons) {
			if (d.damage <= hp) {
				hp += d.difference;
				order.add(d.id);
			} else {
				System.out.println("NIE");
				return;
			}
		}

		for (Dragon d : hardDragons) {
			if (d.damage <= hp) {
				hp += d.difference;
				order.add(d.id);
			} else {
				System.out.println("NIE");
				return;
			}
		}

		System.out.println("TAK");
		
		for (Integer i : order) {
			System.out.print(i);
			System.out.print(" ");
		}

		System.out.println();
	}

	public static class Dragon implements Comparable<Dragon> {
		private int id;
		private int damage;
		private int difference;

		public Dragon(int id, int damage, int heal) {
			this.id = id;
			this.damage = damage;
			difference = heal - damage;
		}

		public boolean isEasy() {
			return difference >= 0;
		}

		@Override
		public int compareTo(Dragon o) {
			return damage - o.damage;
		}
	}
}