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
120
121
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class boh {
	
	public static void main(String[] args) {
		int n = R.i();
		long z = R.i();
		
		PriorityQueue<Potwor> nieujemne = new PriorityQueue<Potwor>(n, new Comparator<Potwor>() {
			@Override
			public int compare(Potwor o1, Potwor o2) {
				// od najmniejszego d
				return o1.d - o2.d;
			}
		});
		PriorityQueue<Potwor> ujemne = new PriorityQueue<Potwor>(n, new Comparator<Potwor>() {
			@Override
			public int compare(Potwor o1, Potwor o2) {
				// od najwiekszego a
				return o2.a - o1.a;
			}
		});
		
		Potwor p;
		for (int i = 1; i <= n; i++) {
			p = new Potwor();
			p.nr = i;
			p.d = R.i();
			p.a = R.i();
			
			if (p.a - p.d >= 0) {
				nieujemne.add(p);
			} else {
				ujemne.add(p);
			}
		}
		
		List<Integer> result = new ArrayList<Integer>(n);
		
		while (!nieujemne.isEmpty()) {
			p = nieujemne.poll();
			z -= p.d;
			if (z <= 0) {
				W.tn(false);
				W.flush();
				return;
			}
			z += p.a;
			result.add(p.nr);
		}
		
		while (!ujemne.isEmpty()) {
			p = ujemne.poll();
			z -= p.d;
			if (z <= 0) {
				W.tn(false);
				W.flush();
				return;
			}
			z += p.a;
			result.add(p.nr);
		}
		
		W.tn(true);
		for (Integer i : result) {
			W.is(i);
		}
		W.flush();
	}
	
	static class Potwor {
		int nr;
		int d;
		int a;
	}
	

	static class R {
		static InputStream is=new BufferedInputStream(System.in);
		static int b='\n';
		static void next(){try{b=is.read();}catch(Exception e){}}
		static void skip(){while(b=='\n'||b==' '||b=='\r'||b=='\t')next();}
		static char c(){skip();char c=(char)b;next();return c;}
		static int i(){skip();int i=0;while(b>='0'&&b<='9'){i=10*i+(b-'0');next();}return i;}
		static long l(){skip();long i=0;while(b>='0'&&b<='9'){i=10*i+(b-'0');next();}return i;}
	}
	static class W {
		static OutputStream os=new BufferedOutputStream(System.out,4096);
		static void b(int b){try{os.write(b);}catch(Exception e){}}
		static void c(char c){b(c);}
		static void cs(char c){c(c);space();}
		static void cn(char c){c(c);newLine();}
		static void i(int i){if(i>9)i(i/10);b('0'+(i%10));}
		static void is(int i){i(i);space();}
		static void in(int i){i(i);newLine();}
		static void l(long l){if(l>9)l(l/10);b('0'+(int)(l%10));}
		static void ls(int l){l(l);space();}
		static void ln(int l){l(l);newLine();}
		static void s(String s){try{os.write(s.getBytes());}catch(Exception e){}}
		static void ss(String s){s(s);space();}
		static void sn(String s){s(s);newLine();}
		static void tn(boolean b){sn(b?"TAK":"NIE");}
		static void space(){b(' ');}
		static void newLine(){b('\n');}
		static void flush(){try{os.flush();}catch(Exception e){}};
	}
	static class T {
		static List<String> s=new ArrayList<String>();
		static List<Long> t=new ArrayList<Long>();
		static void t(String n){s.add(n);t.add(System.currentTimeMillis());}
		static void err(){t.add(System.currentTimeMillis());System.err.println();for(int i=0;i<s.size();i++){System.err.println(s.get(i)+": "+(t.get(i+1)-t.get(i)));}System.err.println("TOTAL: "+(t.get(t.size() - 1)-t.get(0)));System.err.flush();}
	}

}