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
//
//  main.cpp
//  PA_2014_BOH
//
//  Created by Michal Kowalski on 13/05/14.
//  Copyright (c) 2014 Michal Kowalski. All rights reserved.
//

#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

struct E{
    long long val;
    int id;
};

int n,z;
int D[100009];
int A[100009];
long long Z;
vector<E> GM;
vector<E> LM;
int SEQ[100009];
int *pSEQ = SEQ;

bool operator < (const E & e1,const E & e2)
{
    return e1.val > e2.val;
}

int main(int argc, const char * argv[])
{
    scanf("%d %d",&n,&z);
    
    for(int i=1;i<=n;++i)
    {
        int d,a;
        scanf("%d %d",&d,&a);
        D[i]=d;A[i]=a;
        if ((-d+a)>=0)
        {
            E ee;
            ee.val = d;
            ee.id  = i;
            GM.push_back(ee);
        }
        else
        {
            E ee;
            ee.val = a;
            ee.id  = i;
            LM.push_back(ee);
        }
    }
    sort(GM.begin(), GM.end());
    sort(LM.begin(), LM.end());
    
    Z = z;
    int gmsize = (int)GM.size();
    
    for (int i=gmsize-1; i>=0; --i) {
        int m_id = GM[i].id;
        if ( (Z - D[m_id]) > 0)
        {
            Z = Z - D[m_id]+A[m_id];
            *pSEQ = m_id;
            ++pSEQ;
        }
        else
        {
            printf("NIE\n");
            return 0;
        }
    }
    
    for (int i=0; i< LM.size(); ++i) {
        int m_id = LM[i].id;
        if ( (Z - D[m_id]) > 0)
        {
            Z = Z - D[m_id]+A[m_id];
            *pSEQ = m_id;
            ++pSEQ;
        }else
        {
            printf("NIE\n");
            return 0;
        }
    }
    
    printf("TAK\n");
    for(int x=0;x<n;++x)
        printf("%d ",SEQ[x]);
    printf("\n");
    
    return 0;
}