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

/**
 * @author khelman
 */
public class boh {

    public static void main(String... args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String s = reader.readLine();
        String[] elems = s.split(" ");

        int n = Integer.parseInt(elems[0]);
        long z = Integer.parseInt(elems[1]);

        int[] ret = new int[n];
        final long[] ascA = new long[n + 1];
        final long[] ascD = new long[n + 1];
        int retCount = 0;

        PriorityQueue<Integer> ascQueue = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Long.compare(ascD[o1], ascD[o2]);
            }
        });

        PriorityQueue<Integer> dscQueue = new PriorityQueue<Integer>(n, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Long.compare(ascA[o1] - ascD[o1], ascA[o2] - ascD[o2]);
            }
        });

        for (int i = 1; i <= n; i++) {
            s = reader.readLine();
            elems = s.split(" ");

            long d = Integer.parseInt(elems[0]);
            long a = Integer.parseInt(elems[1]);

            ascA[i] = a;
            ascD[i] = d;

            if (a >= d) {
                if (d <= z) {
                    z = z - d + a;
                    ret[retCount++] = i;

                    while (!ascQueue.isEmpty() && ascD[ascQueue.peek()] <= z) {
                        int min = ascQueue.poll();
                        z = z - ascD[min] + ascA[min];
                        ret[retCount++] = min;
                    }
                } else {
                    ascQueue.add(i);
                }
            } else {
                dscQueue.add(i);
            }
        }

        if (!ascQueue.isEmpty()) {
            System.out.println("NIE");
            return;
        }

        while (!dscQueue.isEmpty() && ascD[dscQueue.peek()] <= z) {
            int min = dscQueue.poll();
            z = z - ascD[min] + ascA[min];
            ret[retCount++] = min;
        }

        if (!dscQueue.isEmpty()) {
            System.out.println("NIE");
            return;
        }

        System.out.println("TAK");
        for (int r : ret) {
            System.out.print(r);
            System.out.print(" ");
        }
        System.out.println();

    }
}