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
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

/**
 * @author: Wojciech Krzaczek (wojciech.krzaczek@nsn.com)
 */
public class boh {

	@SuppressWarnings("resource")
	public static void main(String[] args) {

		Scanner scanner = new Scanner(System.in);
		final int numberOfMonsters = scanner.nextInt();
		int health = scanner.nextInt();

		List<int[]> monsters = new ArrayList<int[]>();

		List<Integer> results = new ArrayList<>();

		for (int i = 0; i < numberOfMonsters; i++) {
			final int dmg = scanner.nextInt();
			final int potion = scanner.nextInt();

			int[] monster = { i + 1, (potion - (dmg + 1)) * 1000 / (dmg + 1), dmg, potion };
			monsters.add(monster);
		}
		boh bohater = new boh();
		Collections.sort(monsters, bohater.new monsterComparator());

		while (!monsters.isEmpty()) {
			boolean found = false;
			for (int i = 0; i < monsters.size(); i++) {
				if (health - monsters.get(i)[2] > 0) {
					int[] monster = monsters.remove(i);
					found = true;
					health -= monster[2];
					health += monster[3];
					results.add(monster[0]);
					break;
				}
			}
			if (found) {
				continue;
			}
			System.out.println("NIE");
			return;
		}
		print(results);
	}

	private static void print(List<Integer> results) {
		System.out.println("TAK");
		String resultText = "";
		for (Integer result : results) {
			resultText += result + " ";
		}
		System.out.println(resultText.trim());
	}

	private class monsterComparator implements Comparator<int[]> {

		@Override
		public int compare(int[] monster1, int[] monster2) {
			return monster1[1] < monster2[1] ? 1 : -1;
		}

	}

}