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
program boh;

type
  tab = array[1..100000, 1..3] of longword;

var
  n : longword;
  a : array[1..100000, 1..3] of longword;

  i,j,k : longword;
  z : longint;

  tmp1,tmp2 : longword;
  NO : boolean;

procedure qsort(var t:tab; l,r:longword);
var
  p,tmp : longword;
  i,j : longword;
  begin
    i:=l; j:=r;
    tmp:=(l+r) div 2;
    p:=t[tmp,1];
    repeat
      while t[i,1]<p do i:=i+1;
      while p<t[j,1] do j:=j-1;
      if i<=j then
      begin
        tmp:=t[i,1]; t[i,1]:=t[j,1]; t[j,1]:=tmp;
        tmp:=t[i,2]; t[i,2]:=t[j,2]; t[j,2]:=tmp;
        tmp:=t[i,3]; t[i,3]:=t[j,3]; t[j,3]:=tmp;
        i:=i+1; j:=j-1
      end
    until i>=j;
    if l<j then qsort(t,l,j);
    if i<r then qsort(t,i,r)
  end;
procedure qsort1(var t:tab; l,r:longword);
var
  p,q,tmp : longword;
  i,j : longword;
  begin
    i:=l; j:=r;
    tmp:=(l+r) div 2;
    p:=t[tmp,1];
    q:=t[tmp,2];
    repeat
      while (t[i,1]<p) or ((t[i,1]=p) and (t[i,2]<q)) do i:=i+1;
      while (p<t[j,1]) or ((t[j,1]=p) and (t[j,2]>q)) do j:=j-1;
      if i<=j then
      begin
        tmp:=t[i,1]; t[i,1]:=t[j,1]; t[j,1]:=tmp;
        tmp:=t[i,2]; t[i,2]:=t[j,2]; t[j,2]:=tmp;
        tmp:=t[i,3]; t[i,3]:=t[j,3]; t[j,3]:=tmp;
        i:=i+1; j:=j-1
      end
    until i>=j;
    if l<j then qsort1(t,l,j);
    if i<r then qsort1(t,i,r)
  end;

begin
  readln(n,z);

  j:=0; k:=n+1;
  for i:=1 to n do
  begin
    readln(tmp1,tmp2);
    if tmp2>tmp1 then
    begin
      j:=j+1; a[j,1]:=tmp1; a[j,2]:=tmp2; a[j,3]:=i
    end
    else
    begin
     k:=k-1; a[k,1]:=tmp1; a[k,2]:=tmp2; a[k,3]:=i
    end
  end;
  if j>1 then qsort(a,1,j);
  if k<n then qsort1(a,k,n);
  i:=1;
  if j>0 then
  repeat
    if z>a[i,1] then
    begin
      z:=z-a[i,1]+a[i,2]; i:=i+1
    end
    else NO:=true
  until (i>j) or NO;
  i:=n;
  if (k<=n) and not NO then
  repeat
    if z>a[i,1] then
    begin
      z:=z-a[i,1]+a[i,2]; i:=i-1
    end
    else NO:=true
  until (i<k) or NO;
  if NO then writeln('NIE')
  else
  begin
    writeln('TAK');
    if j>0 then
    begin
      write(a[1,3]);
      for i:=2 to j do
        write(' ',a[i,3])
    end;
    for i:=n downto k do
      write(' ',a[i,3]);
    writeln;
  end;
end.