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

public class boh {

	private class Potwor {
		private int id;
		private int koszt;
		private int zysk;

		public Potwor(int id, int koszt, int zysk) {
			this.id = id;
			this.koszt = koszt;
			this.zysk = zysk;
		}

		public int getDifference() {
			return zysk - koszt;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		boh inst = new boh();
		long a = System.currentTimeMillis();
	//	System.setIn(new FileInputStream("c:\\potyczki\\data.txt"));
		BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));

		String[] dane = bi.readLine().split(" ");
		int iloscPotworow = Integer.parseInt(dane[0]);
		int zycie = Integer.parseInt(dane[1]);

		Potwor[] array = new Potwor[iloscPotworow];
		for (int i = 0; i < iloscPotworow; i++) {
			String[] costs = bi.readLine().split(" ");
			array[i] = inst.new Potwor(i+1, Integer.parseInt(costs[0]), Integer.parseInt(costs[1]));

		}

		Arrays.sort(array, new Comparator<Potwor>() {

			@Override
			public int compare(Potwor a0, Potwor a1) {
				return a1.getDifference() - a0.getDifference();
			}
		});

		int podzial = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i].getDifference() < 0) {
				podzial = i;
				break;
			}
		}
		Potwor[] dobrePotwory = Arrays.copyOfRange(array, 0, podzial);
		Potwor[] zlePotwory = Arrays.copyOfRange(array, podzial, array.length);
		Arrays.sort(dobrePotwory, new Comparator<Potwor>() {

			@Override
			public int compare(Potwor a0, Potwor a1) {
				return a0.koszt - a1.koszt;
			}
		});

		Arrays.sort(zlePotwory, new Comparator<Potwor>() {

			@Override
			public int compare(Potwor a0, Potwor a1) {
				return a1.koszt - a0.koszt;
			}
		});
		for (Potwor potwor : dobrePotwory) {
			zycie -= potwor.koszt;	
			if (zycie <= 0) break;
			zycie+= potwor.zysk;
		}
	
		if (zycie >= 0)
		for (Potwor potwor : zlePotwory) {
			zycie -= potwor.koszt;	
			if (zycie <= 0) break;
			zycie+= potwor.zysk;
		}
		
		if (zycie <= 0) {
			System.out.println("NIE");
		} else {
			System.out.println("TAK");
			for (Potwor potwor : dobrePotwory) 
				System.out.print(potwor.id + " "); 
			for (Potwor potwor : zlePotwory) 
				System.out.print(potwor.id + " ");
		}
		
		//System.out.println("time = " + (System.currentTimeMillis() - a));
	}

}