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

using namespace std;

struct monster
{
    int id;
    int a;
    int b;
    monster( int _id, int _a, int _b ) :
        id(_id),a(_a),b(_b) {}
};

int cmp2( monster const& a, monster const& b )
{
    if( a.a + a.b != b.a + b.b )
    {
        return (a.a + a.b) > ( b.a + b.b );
    }
    return a.b > b.b;
}


bool cmp(  monster const& a,  monster const& b )
{
    return a.a < b.a;
}

vector< monster > positive;
vector< monster > negative;



int main()
{
    int n,z;
    scanf( "%d%d", &n, &z );

    for( int i = 0 ; i < n; ++i )
    {
        int a,b;
        scanf( "%d%d", &a, &b );
        if( b >= a  )
            positive.push_back( monster( i + 1, a, b - a ) );
        else
            negative.push_back( monster( i + 1, a, b - a ) );
    }

    sort( positive.begin(), positive.end(), cmp );

    for( int i = 0; i < positive.size(); ++i )
    {
        if( positive[i].a >= z )
        {
            printf( "NIE\n" );
            return 0;
        }
        //printf( "%d %d\n", positive[i].a, positive[i].a + positive[i].b );
        z+= positive[i].b;
    }

    //printf( "NEgative\n" );

    sort( negative.begin(), negative.end(), cmp2 );

    for( int i = 0; i < negative.size(); ++i )
    {
        if( negative[i].a >= z )
        {
            printf( "NIE\n" );
            return 0;
        }
        //printf( "%d %d\n", negative[i].a, negative[i].a + negative[i].b );
        z += negative[i].b;
    }
    printf( "TAK\n" );

    for( int i = 0 ; i < positive.size(); ++i )
    {
        printf( "%d ", positive[i].id );
    }

    for( int i = 0 ; i < negative.size(); ++i )
    {
        printf( "%d ", negative[i].id );
    }

    return 0;
}