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

public class boh {

    public static Monster getMonster(int index, int dmg, int hp) {
        Monster m = new Monster();
        m.index = index + 1;
        m.damage = dmg;
        m.hp = hp;
        m.diff = hp - dmg;
        return m;
    }

    public static void seperate(List<Monster> monsters, List<Monster> alive, List<Monster> dead) {
        List<Monster> zeros = new ArrayList<>();
        for (Monster m : monsters) {
            if (m.diff == 0) {
                zeros.add(m);
            } else {
                if (m.diff > 0) {
                    alive.add(m);
                } else {
                    dead.add(m);
                }
            }
        }

        Collections.sort(alive, new Comparator<Monster>() {
            @Override
            public int compare(Monster a, Monster b) {
                int cmp = a.damage < b.damage ? -1 : a.damage == b.damage ? 0 : 1;
                if (cmp == 0) {
                    cmp = a.hp < b.hp ? 1 : a.hp == b.hp ? 0 : -1;
                }
                return cmp;
            }
        });

        alive.addAll(zeros);

        Collections.sort(dead, new Comparator<Monster>() {
            @Override
            public int compare(Monster a, Monster b) {
                int cmp = a.hp < b.hp ? 1 : a.hp == b.hp ? 0 : -1;

                if (cmp == 0) {
                    cmp = a.damage < b.damage ? -1 : a.damage == b.damage ? 0 : 1;
                }
                return cmp;
            }
        });


    }

    public static void simulate(List<Monster> list, int hp) {
        for (Monster m : list) {
            hp -= m.damage;
            hp += m.hp;
        }
        System.out.println(hp > 0 ? "TAK" : "NIE");
    }

    public static void main(String[] args) {
        try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            int monsters = Integer.parseInt(st.nextToken());
            int heroHP   = Integer.parseInt(st.nextToken());
            List<Monster> list = new ArrayList<>(monsters);

            for (int m = 0; m < monsters; m++) {
                st = new StringTokenizer(in.readLine());
                Monster mn = getMonster(m, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
                list.add(mn);
            }

            List<Monster> alive = new ArrayList<>(monsters/2 + 1);
            List<Monster> dead = new ArrayList<>(monsters/2 + 1);

            seperate(list, alive, dead);

            alive.addAll(dead);

            simulate(list, heroHP);

            StringBuilder sb = new StringBuilder(alive.size() * 2);
            for (Monster m: alive) {
                sb.append(m.index);
                sb.append(" ");
            }
            System.out.print(sb.toString());

        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static class Monster{
        int index;
        int damage;
        int hp;
        int diff;

        public String toString() {
            return index + "";
        }
    }
}