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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class boh {

    public static void main(final String[] args) {

        final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            String[] line = reader.readLine().trim().split("\\s+");
            int rows = Integer.parseInt(line[0]);
            int stamina = Integer.parseInt(line[1]);
            List<Enemy> enemies = new ArrayList<Enemy>();
            for (int i = 0; i < rows; i++) {
                line = reader.readLine().trim().split("\\s+");
                int damage = Integer.parseInt(line[0]);
                int recovery = Integer.parseInt(line[1]);
                enemies.add(new Enemy(damage, recovery, i + 1));
            }

            Stack<Enemy> stack = new Stack<Enemy>();
            downTheWay(stamina, enemies, stack);
            System.out.println("NIE");

        } catch (IOException e) {
            e.printStackTrace();
        }
        System.exit(0);
    }

    private static void downTheWay(int stamina, List<Enemy> enemies, Stack<Enemy> stack) {
        for(int i=0; i<enemies.size(); i++)
        {
            Enemy chosen = enemies.remove(i);
            if (stamina > chosen.damage) {
                stack.push(chosen);
                if(enemies.isEmpty())
                {
                    System.out.println("TAK");
                    StringBuilder sb = new StringBuilder();
                    for(int j = 0; j<stack.size();j++)
                    {
                        sb.append(stack.get(j).idx).append(" ");
                    }
                    System.out.println(sb.toString());
                    System.exit(0);

                }
                downTheWay(stamina - chosen.damage + chosen.recovery, enemies, stack);
                stack.pop();
            }
            enemies.add(i, chosen);
        }
    }

    private static final class Enemy {
        public final int damage;
        public final int recovery;
        public final int idx;

        public Enemy(int damage, int recovery, int idx) {
            this.damage = damage;
            this.recovery = recovery;
            this.idx = idx;
        }
    }

}