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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
import java.io.*;
import java.util.*;

/**
 * Created by Bogumil Sikora.
 */
public class boh {

    private static List<Integer> result = new ArrayList<Integer>();

    public static void main(String[] args) throws Exception {
        Reader.init(System.in);
        PrintWriter pw = new PrintWriter(System.out);

        int N = Reader.nextInt();
        int Z = Reader.nextInt();

        List<Monster> adding = new ArrayList<Monster>();
        List<Monster> removing = new ArrayList<Monster>(); // minus
        List<Monster> equal = new ArrayList<Monster>();

        for (int i = 1; i <= N; i++) {
            int d = Reader.nextInt();
            int a = Reader.nextInt();

            if (a >= d && Z > d) { // if adding or equal and we can beat him.
                result.add(i);
                Z -= d;
                Z += a;
            } else {
                Monster p = new Monster();
                p.idx = i;
                p.d = d;
                p.a = a;
                if (a > d) {
                    adding.add(p);
                } else if (a == d) {
                    equal.add(p);
                } else {
                    removing.add(p);
                }
            }
        }

        Collections.sort(adding);
        Collections.sort(removing, FromTheStrongest);

        boolean ok = true;

        Z = conquer(Z, adding);

        if (Z > 0) {
            Z = conquer(Z, equal);
        } else {
            ok = false;
        }

        if (Z > 0) {
            Z = conquer(Z, removing);
        }

        if (Z <= 0) {
            ok = false;
        }

        if (ok && result.size() == N) {
            pw.println("TAK");
            for (Integer idx : result) {
                pw.print(idx + " ");
            }
        } else {
            pw.println("NIE");
        }

        pw.flush();
        pw.close();
        Reader.close();

    }

    public static int conquer(int initialZ, List<Monster> monsters) {
        for (Monster monster : monsters) {
            if (initialZ <= monster.d) {
                return -1;
            }
            result.add(monster.idx);
            initialZ -= monster.d;
            initialZ += monster.a;
        }

        return initialZ;
    }

    public static Comparator<Monster> FromTheStrongest = new Comparator<Monster>() {

        public int compare(Monster m1, Monster m2) {
            return -Integer.valueOf(m1.d).compareTo(m2.d);
        }

    };

    static class Monster implements Comparable<Monster> {
        int idx;
        int d;
        int a;

        @Override
        public int compareTo(Monster o) {
            return Integer.valueOf(this.d).compareTo(o.d);
        }
    }

    static class Reader {
        static BufferedReader reader;
        static StringTokenizer tokenizer;

        static void init(InputStream input) {
            reader = new BufferedReader(new InputStreamReader(input));
            tokenizer = new StringTokenizer("");
        }

        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens() ) {
                tokenizer = new StringTokenizer(reader.readLine() );
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt( next() );
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble( next() );
        }

        static void close() throws IOException {
            reader.close();
        }
    }
}