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
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

class DataPoint {
    int i;
    int d;
    int a;
    int diff;
    
    public DataPoint(int i, int d, int a) {
        this.i = i;
        this.d = d;
        this.a = a;
        this.diff = a - d;
    }

    @Override
    public String toString() {
        return "i=" + (i + 1) + ", d=" + d + ", a=" + a + ", diff=" + diff;
    }
}

class DiffComparator implements Comparator<DataPoint> {

    @Override
    public int compare(DataPoint o1, DataPoint o2) {
        return o2.diff - o1.diff;
    }
}

class DComparator implements Comparator<DataPoint> {
    @Override
    public int compare(DataPoint o1, DataPoint o2) {
        return o2.d - o1.d;
    }
}

public class boh {

    
    
    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        Scanner scanner = new Scanner(System.in);
        
        int n, z;
        n = scanner.nextInt();
        z = scanner.nextInt();
        
        List<DataPoint> dp = new LinkedList<DataPoint>();
        for (int i = 0; i < n; i++) {
            int d_i = scanner.nextInt();
            int a_i = scanner.nextInt();
            
            dp.add(new DataPoint(i, d_i, a_i));
        }
        
        
//        System.out.println("Faza 1.");
        Collections.sort(dp, new DiffComparator());
        
//        for (int i = 0; i < n; i++) {
//            System.out.println("dp[" + i + "]=" + dp.get(i));
//        }
        
        int[] path = new int[n];
        int pathCnt = 0;
        for (int i = 0; i < n; i++) {
//            System.out.println("i=" + i);
            if (dp.get(0).diff < 0) {
                break;
            }
            for (int j = 0; j < n - i; j++) {
                DataPoint currDP = dp.get(j);
//                System.out.println("cd=[" + currDP + "]");
                if (currDP.d < z) {
                    z += currDP.diff;
                    path[i] = currDP.i;
                    pathCnt = i;
                    dp.remove(j);
                    break;
                }
            }
        }
        
        //skonczylismy z dodatnimi - czas na etap 2.!
//        System.out.println("Faza 2.");
        Collections.sort(dp, new DComparator());
//        for (int i = 0; i < dp.size(); i++) {
//            System.out.println("dp[" + i + "]=" + dp.get(i));
//        }
        
        boolean winner = true;
        for (int i = 0; i < dp.size(); i++) {
            DataPoint currDP = dp.get(i);
            z += currDP.diff;
            if (z <= 0) {
                winner = false;
                break;
            }
            path[++pathCnt] = currDP.i;
        }
        
        if (winner) {
            System.out.println("TAK");
            for (int i = 0; i < n; i++) {
                System.out.print((path[i] + 1) + " ");
            }
            System.out.println();
        } else {
            System.out.println("NIE");
        }
        
//        System.err.println("Time: " + (System.currentTimeMillis() - start));
    }
}