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

using namespace std;

int D[100005];
int A[100005];
int B[100005];
int S[100005];

bool sort_funca( int i, int j )
{
    return D[i]<D[j];
}

bool sort_funcb( int i, int j )
{
    return A[i]>A[j];
}

int main()
{
    int n,z;
    scanf("%d%d",&n,&z);
    long long s=z;
    
    int ils=0,ilsb;
    for ( int i=0; i<n; i++ )
        {
            scanf("%d%d",D+i,A+i);
            B[i]=A[i]-D[i];
            if ( B[i]>=0 )
               S[ils++]=i;
            s+=B[i];
            //printf("%d %d\n",D[i],B[i]);
        }
    //printf("\n");
    //printf("%lld\n",s);
    if ( s<=0 ) goto _fail;
    
    sort( S, S+ils, sort_funca );
    
    s=z;
    for ( int ii=0; ii<ils; ii++ )
        {
            int i = S[ii];
            if ( s<=D[i] ) goto _fail;
            s+=B[i];
        }
    
    ilsb=ils;
    for ( int i=0; i<n; i++ )
        {
            if ( B[i] < 0 )
               S[ilsb++]=i;
        }
    
    sort( S+ils, S+n, sort_funcb );
    
    for ( int ii=ils; ii<n; ii++ )
        {
            int i = S[ii];
            //printf("aaaaa %lld %d\n",s,D[i]);
            if ( s<=D[i] ) goto _fail;
            s+=B[i];
        }
    
    printf("TAK\n");
    for ( int i=0; i<n; i++ ) printf("%d ",S[i]+1); printf("\n");
    return 0;
    
    _fail:;
    printf("NIE\n");
    return 0;
}