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

public class boh {
    static class MO {
        final int d, i, a;

        MO(int d, int a, int i) {
            this.d = d;
            this.a = a;
            this.i = i;
        }

        @Override
        public String toString() {
            return "{d: " + d + " a: " + a + " i: " + i + "}";
        }
    }

    private static final InputStream in = new BufferedInputStream(System.in);

    private static int readInt() {
        try {
            int ret = 0, b;
            while ((b = in.read()) != -1) if (b != ' ' && b != '\r' && b != '\n') break;
            do if (b < '0' || b > '9') break;
            else ret = ret * 10 + (b - '0'); while ((b = in.read()) != -1);
            return ret;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    public static void main(String... args) {
        int n = readInt();
        int z = readInt();
        List<Integer> res = new ArrayList<>(n);
        List<MO> mosUp = new ArrayList<>(n);
        List<MO> mosDn = new ArrayList<>(n);
        for (int i = 0; i < n; ++i) {
            int d = readInt();
            int a = readInt();
            if (a > d) {
                if (d < z) {
                    z += a - d;
                    res.add(i);
                } else mosUp.add(new MO(d, a, i));
            } else mosDn.add(new MO(d, a, i));
        }
        Collections.sort(mosUp, (a, b) -> a.d - b.d);
        Collections.sort(mosDn, (a, b) -> b.d - a.d);
        for (MO mo : mosUp) {
            z -= mo.d;
            if (z <= 0) {
                break;
            }
            z += mo.a;
            res.add(mo.i);
        }
        for (MO mo : mosDn) {
            z -= mo.d;
            if (z <= 0) {
                break;
            }
            z += mo.a;
            res.add(mo.i);
        }
        if (z <= 0) {
            System.out.println("NIE");
        } else {
            System.out.println("TAK");
            String s = "";
            for (Integer i : res) {
                System.out.print(s); s = " "; System.out.print(i + 1);
            }
            System.out.println();
        }

    }
}