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
#include <iostream>
#include <algorithm>

using namespace std;

const int nmax =  100000;

int D[nmax], A[nmax], s[nmax];

bool mcmp(int i, int j)
{
  int d1,d2, a1,a2, r1,r2 ;
  
  d1=D[i]; a1=A[i]; r1=a1-d1;
  d2=D[j]; a2=A[j]; r2=a2-d2;

  if ((r1< 0)&&(r2< 0)) 
  {
/*
    if (r1==r2) 
    {
      return (d1<d2);
    }
    else
      return (r1>r2);
/**/
//*
    if (d1!=d2) 
    {
      return (d1>d2);
    }
    else
      return (r1>r2);
/**/      
  }

  if ((r1>=0)&&(r2>= 0)) 
  {
    if (d1!=d2) 
    {
      return (d1<d2);
    }
    else
      return (r1<r2);
  }

  return (r1>=0);
}

bool mcmp1(int i, int j)
{
  int x;
  int d1,d2, a1,a2, r1,r2 ;
  
  x=mcmp(i,j);
  d1=D[i]; a1=A[i]; r1=a1-d1;
  d2=D[j]; a2=A[j]; r2=a2-d2;

  cout<<i<<":"<<j<<" Q " 
    <<" a="<<d1<<":"<<a1<<"="<<r1
    <<" b="<<d2<<":"<<a2<<"="<<r2
    <<" x="<<x
    <<endl;
  return x;
}

int main()
{
  int n,n1;
  
  long long z,zz;
  
  cin.sync_with_stdio(false); // !!!!!!!!!!!!!!!!
  
  cin >>n >>z;
  zz=z;
  for( int i=0; i<n; i++) { s[i]=i; cin >>D[i] >>A[i];  zz+=A[i]-D[i];}
  if (zz<=0) { cout <<"NIE"<<endl; return 0; }
  
  sort(s,s+n,mcmp);
/*
cout<<"z="<<z<<endl;
for(int i=0;i<n;i++)cout <<s[i]<<' ';cout<<endl;
for(int i=0;i<n;i++)cout <<i<<'='<<D[i]   <<':'<<A[i]   <<' ';cout <<endl;
for(int i=0;i<n;i++)cout <<i<<'='<<D[s[i]]<<':'<<A[s[i]]<<' ';cout <<endl;
zz=z;for(int i=0;i<n;i++){cout <<i<<'='<<zz<<"+"<<D[s[i]]<<':'<<A[s[i]]<<' ';zz+=A[s[i]]-D[s[i]];}cout <<endl;
/**/
  
  n1=0;
  for( int i=0,a,d; i<n; i++) 
  {
    d=D[s[i]];
    a=A[s[i]];
    if ((a-d)>=0) n1=i+1;
    z-=d;
    if (z<=0) { cout <<"NIE"<<endl; return 0; }
    z+=a;
  }

  cout <<"TAK"<<endl;
  for( int i=0; i<n-1; i++) cout<<s[i]+1<<" ";
  cout <<s[n-1]+1<<endl;
  
//  for( int i=0; i<n; i++) if(

//cout<<"s= ";for( int i=0; i<n; i++)  cout<<s[i]<<' ';cout<<endl;


}