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

/**
 * Created by konrad on 13.05.14.
 */
public class boh {

    public static List<Monster> solve(List<Monster> monsters, int live)
    {
        Iterator<Monster> mit = monsters.iterator();
        List<Monster> orderedMonsters = new ArrayList<>(monsters.size());
        while (mit.hasNext())
        {
            Monster m = mit.next();
            orderedMonsters.add(m);
            live -= m.d;
            if (live <= 0) return null;
            live += m.a;
        }
        return orderedMonsters;
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ints = br.readLine().split(" ");
        int n = Integer.parseInt(ints[0]);
        int z = Integer.parseInt(ints[1]);
        int i = 0;
        List<Monster> positives = new ArrayList<>();
        List<Monster> negatives = new ArrayList<>();
        while (i++ < n) {
            ints = br.readLine().split(" ");
            Monster m = new Monster(i, Integer.parseInt(ints[0]), Integer.parseInt(ints[1]));
            if (m.gain <= 0)
                negatives.add(m);
            else
                positives.add(m);
        }
        Collections.sort(positives, (Monster m1, Monster m2) -> Integer.compare(m1.d, m2.d));
        Collections.sort(negatives, (Monster m1, Monster m2) -> -Integer.compare(m1.d, m2.d));
        positives.addAll(negatives);
        positives = solve(positives, z);
        if (positives == null) {
            System.out.println("NIE");
            System.exit(0);
        }
        System.out.println("TAK");
        Iterator<Monster> it = positives.iterator();
        System.out.print(it.next().number);
        while (it.hasNext()) System.out.print(" " + it.next().number);
        System.out.println();
        System.out.flush();
    }

    public static class Monster
    {
        public Monster(int number, int d, int a)
        {
            this.number = number;
            this.a = a;
            this.d = d;
            this.gain = a - d;
        }
        int number;
        int a;
        int d;
        int gain;

    }
}