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
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class boh {
    public static void main(String[] args) {
        new boh().executeAll(System.in, System.out);
    }

    void executeAll(InputStream in, PrintStream out) {
        Scanner scanner = new Scanner(in);

        int numberOfMonsters = scanner.nextInt();
        int initialPower = scanner.nextInt();

        Fight[] fights = new Fight[numberOfMonsters];
        Fight.monsterCount = 0;
        Fight fight;
        int first=0;
        int last = numberOfMonsters-1;
        for (int i = 0; i < numberOfMonsters; i++) {
            fight = new Fight(scanner.nextInt(), scanner.nextInt());
            if (fight.monstersPower <= fight.elicsirPower) {
                fights[first++] = fight;
            } else {
                fights[last--] = fight;
            }
        }
        assert first == last;

        Fight[] increasingFights = new Fight[first];
        Fight[] decreasingFights = new Fight[numberOfMonsters-first];
        System.arraycopy(fights, 0, increasingFights, 0, increasingFights.length);
        System.arraycopy(fights, first, decreasingFights, 0, decreasingFights.length);

        if (doJob(initialPower, increasingFights, decreasingFights)) {
            out.println("TAK");
            for (Fight f : increasingFights)
                out.print(f.monsterNumber + " ");
            for (Fight f : decreasingFights)
                out.print(f.monsterNumber + " ");
        } else {
            out.println("NIE");
        }
    }

    static class Fight {
        static int monsterCount = 0;
        int monsterNumber = ++monsterCount;

        int monstersPower;
        int elicsirPower;

        public Fight(int monstersPower, int elicsirPower) {
            this.monstersPower = monstersPower;
            this.elicsirPower = elicsirPower;
        }
    }

    boolean doJob(int power, Fight[] increasingFights, Fight[] decreasingFights) {

        // fights that increase final power
        if (increasingFights.length > 0) {
            // sort them in the order of increasing monster power
            Arrays.sort(increasingFights, new Comparator<Fight>() {
                @Override
                public int compare(Fight o1, Fight o2) {
                    return o1.monstersPower - o2.monstersPower;
                }
            });

            for (Fight fight : increasingFights) {
                power -= fight.monstersPower;
                if (power <= 0)
                    return false;
                power += fight.elicsirPower;
            }
        }

        // fights that decrease final power
        if (decreasingFights.length > 0) {
            // sort them in the order of decreasing elicsir power
            Arrays.sort(decreasingFights, new Comparator<Fight>() {
                @Override
                public int compare(Fight o1, Fight o2) {
                    return o2.elicsirPower - o1.elicsirPower;
                }
            });

            for (Fight fight : decreasingFights) {
                power -= fight.monstersPower;
                if (power <= 0)
                    return false;
                power += fight.elicsirPower;
            }
        }

        return true;
    }
}