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

/**
 * @author jsowicki 13.05.14.
 */
public class boh {
    static int startingHp;
    static int sumOfGains = 0;

    public static void main (String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String firstInputLine = reader.readLine();
        String inputLine;
        int d, a;
        int monstersCount = Integer.parseInt(firstInputLine.split(" ")[0]);
        startingHp = Integer.parseInt(firstInputLine.split(" ")[1]);
        int currentHp = startingHp;
        ArrayList<int[]> allMonsters = new ArrayList<int[]>();
        ArrayList<int[]> positiveMonsters = new ArrayList<int[]>();
        ArrayList<int[]> negativeMonsters = new ArrayList<int[]>();
        ArrayList<int[]> resultsOrder = new ArrayList<int[]>();

        for (int i = 0; i < monstersCount; i++) {
            int monsterInfo[] = new int[3];
            inputLine = reader.readLine();

            d = Integer.parseInt(inputLine.split(" ")[0]);
            a = Integer.parseInt(inputLine.split(" ")[1]);

            // 4 elements: dmg, heal, heal-dmg, number before sorting
            monsterInfo[0] = i+1;
            monsterInfo[1] = d;
            monsterInfo[2] = a;

            sumOfGains += (a-d);

            allMonsters.add(monsterInfo);
        }

        for (int[] monster : allMonsters) {
            if( (monster[2] - monster[1]) >= 0)
            {
                positiveMonsters.add(monster);
            } else {
                negativeMonsters.add(monster);
            }
        }

        Collections.sort(positiveMonsters, new MonsterComparatorByDamage());
        // z dodatnim zyskiem sprawdzone i dodane do kolejki wynikow
        for (int[] monster : positiveMonsters) {
            if (monster[1] >= currentHp) {
                System.out.println("NIE");
                return;
            }

            currentHp = currentHp - monster[1] + monster[2];
            resultsOrder.add(monster);
        }

        Collections.sort(negativeMonsters, new MonsterComparatorByGains());

        for (int[] monster : negativeMonsters) {
            resultsOrder.add(monster);
        }

        // sprawdzenie poprawnosci
        currentHp = startingHp;
        for (int[] monster : resultsOrder) {
            if (currentHp > monster[1]) currentHp = currentHp - monster[1] + monster[2];
            else {
                System.out.println("NIE");
                return;
            }
        }

        // print results
        System.out.println("TAK");
        for (int[] monster : resultsOrder) {
            System.out.print(monster[0] + " ");
        }
		System.out.println("");

    }

    static class MonsterComparatorByDamage implements Comparator<int[]> {
        @Override
        public int compare(int[] o1, int[] o2) {
            return (o1[1] - o2[1]);
        }
    }

    static class MonsterComparatorByGains implements Comparator<int[]> {
        @Override
        public int compare(int[] o1, int[] o2) {
            int first = boh.startingHp + boh.sumOfGains - (o1[2] - o1[1]) - o1[1] + 1;
            int second = boh.startingHp + boh.sumOfGains - (o2[2] - o2[1]) - o2[1] + 1;
            return first - second;
        }
    }

}