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


public class boh {
    static class Fight {
        int number;
        long damage;
        long elixir;

        Fight(int number, long damage, long elixir) {
            this.number = number;
            this.damage = damage;
            this.elixir = elixir;
        }

        public long gain() {
            return this.elixir - this.damage;
        }
    }

    public static void main(String[] args) throws IOException {
        PriorityQueue<Fight> winnable = new PriorityQueue<Fight>(1000, new Comparator<Fight>() {
            @Override
            public int compare(Fight left, Fight right) {
                // Prefer fights where hero gains more health
                return Long.signum(right.gain() - left.gain());
            }
        });
        PriorityQueue<Fight> unwinnable = new PriorityQueue<Fight>(1000, new Comparator<Fight>() {
            @Override
            public int compare(Fight left, Fight right) {
                // Prefer fights where hero takes less damage
                return Long.signum(left.damage - right.damage);
            }
        });

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] tokens = reader.readLine().split(" ");
        int n = Integer.parseInt(tokens[0]);
        long health = Long.parseLong(tokens[1]);

        for (int i = 1; i <= n; i++) {
            tokens = reader.readLine().split(" ");
            long d = Long.parseLong(tokens[0]);
            long a = Long.parseLong(tokens[1]);
            if (d >= health) {
                unwinnable.add(new Fight(i, d, a));
            } else {
                winnable.add(new Fight(i, d, a));
            }
        }

        ArrayList <Fight> fights = solution(health, winnable, unwinnable);
        if (fights == null) {
            System.out.println("NIE");
        } else {
            System.out.println("TAK");
            String first = "";
            for (Fight fight : fights) {
                System.out.print(first + fight.number);
                first = " ";
            }
            System.out.println();
        }
    }

    private static ArrayList<Fight> solution(long health, PriorityQueue<Fight> winnable, PriorityQueue<Fight> unwinnable) {
        ArrayList<Fight> fights = new ArrayList<Fight>();
        PriorityQueue<Fight> lastStreak = new PriorityQueue<Fight>(1000, new Comparator<Fight>() {
            @Override
            public int compare(Fight left, Fight right) {
                // Prefer fights where hero takes more damage
                return Long.signum(right.damage - left.damage);
            }
        });

        while (!winnable.isEmpty()) {
            Fight fight = winnable.poll();
            if (fight.gain() < 0) {
                lastStreak.add(fight);
            } else {
                fights.add(fight);
                health += fight.gain();
                while (!unwinnable.isEmpty() && unwinnable.peek().damage < health) {
                    winnable.add(unwinnable.poll());
                }
            }
        }

        if (!unwinnable.isEmpty()) {
            return null;
        }

        while (!lastStreak.isEmpty()) {
            Fight fight = lastStreak.poll();
            fights.add(fight);
            if (health - fight.damage <= 0) {
                return null;
            }
            health += fight.gain();
        }

        return fights;
    }
}