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

using namespace std;


void qs( int tab[],int tab2[],int tab3[], int left, int right )
{
    int i = left;
    int j = right;
    int x = tab[( left + right ) / 2 ];
    do
    {
        while( tab[ i ] < x )
             i++;
        
        while( tab[ j ] > x )
             j--;
                     
        if( i <= j )
        {
            swap( tab[ i ], tab[ j ] );
            swap( tab2[ i ], tab2[ j ] );
            swap( tab3[ i ], tab3[ j ] );
            i++;
            j--;
        }
    } while( i <= j );
    if( left < j ) qs( tab,tab2,tab3, left, j );
    if( right > i ) qs( tab,tab2,tab3, i, right );
    
}

int add1[100001],add2[100001],add3[100001];
int sub1[100001],sub2[100001],sub3[100001];
int result[100001];
int result2[100001];

int main(){
            
    int i,j,a,b,n,z,add,sub,rescounter;
    long long earned=0;
    long long uwalimy=0;
    add=0;
    sub=0;
    
    scanf("%d%d",&n,&z);
    earned=z;
    for(i=0;i<n;i++){
          scanf("%d%d",&a,&b);
          if(a<=b){
                  add1[add]=a; // wymagany
                  add2[add]=b-a; // zysk
                  add3[add++]=i;
          }
          else{
               uwalimy=uwalimy + b - a;
               sub1[sub]=b; // wymagany
               sub2[sub]=a-b; // tyle dostaniemy
               sub3[sub++]=i;
          }
    }
    qs(add1,add2,add3,0,add-1);
    qs(sub1,sub2,sub3,0,sub-1);
    
    for(i=0;i<add;i++){
             if(add1[i]<earned){
                  earned+=(long long)add2[i];  
                  result[i]=add3[i];             
             }          
             else
                  break;
    }
    
    if(i!=add){
               printf("NIE\n");
    }
    else{
      //  cout<<earned<<" sciepa\n";
        earned = earned + uwalimy;
      //  cout<<earned<<" sciepa po VAT\n";
        if(earned<=0)
                     printf("NIE\n");
        else{
        
            for(i=0;i<sub;i++){
           //      cout<<"anal:"<<sub1[i]<<","  <<sub2[i]<<","<<sub3[i]<<"\n";            
                 if(sub1[i]<earned){
                      earned+=(long long)sub2[i];  
                      result2[i]=sub3[i];             
                 }          
                 else
                      break;
            }   
            if(i!=sub){
                       printf("NIE\n");
            }
            else{
                       printf("TAK\n");
                       for(i=0;i<add;i++)
                          printf("%d ",result[i]+1);
                       for(i=sub-1;i>=0;i--)
                          printf("%d ",result2[i]+1);
                 
            }
        }
    }
}