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
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

typedef struct
{
    int d;
    int a;
    int i;
} d_a;

int cmp_keys( const void* a, const void* b )
{
    const d_a* aa = (const d_a*)a;
    const d_a* bb = (const d_a*)b;
    int za = aa->a - aa->d;
    int zb = bb->a - bb->d;
    if( za >= 0 && zb >= 0  )
        return aa->d - bb->d;
    else if ( za >= 0 ) return -1;
    else if ( zb >= 0 ) return  1;
    {
        int A0 = aa->d;
        int A1 = bb->d;
        if ( bb->d - za > A0 ) A0 = bb->d - za;
        if ( aa->d - zb > A1 ) A1 = aa->d - zb;
        if ( A0 < A1 ) return -1;
        if ( A0 > A1 ) return 1;
        return bb->d - aa->d;
    }   
}

int main()
{
    int n, i, cr, cd, *res;
    d_a *data;
    long long int z, sa, sd;
    scanf( "%d%d", &n, &i );
    z = i;
    sa = sd = 0;
    data = malloc( sizeof(d_a) * n );
    res = malloc( sizeof(int) * n );
    cd = cr = 0;
    for ( i = 0; i < n; ++i )
    {
        int d, a;
        scanf( "%d%d", &d, &a );
        sa += a;
        sd += d;
        if ( a-d >= 0 && d < z )
        {
            z += a-d;
            res[ cr++ ] = i + 1;
        }
        else
        {
            data[ cd ].d = d;
            data[ cd ].a = a;
            data[ cd ].i = i + 1;
            ++cd;
        }
    }
    if ( sa + z > sd )
    {    
        /*fprintf( stderr, "%d %d %d %lld\n", cd, cr, n, z );*/
        qsort( data, cd, sizeof(d_a), cmp_keys );
        for ( i = 0; i < cd; ++i )
        {
            int d, a;
            d = data[i].d;
            a = data[i].a;
            /*fprintf(stderr,"\t%d %d\n",d,a);*/
            if ( d >= z ) break;
            else if ( d < z )
            {
                z += a-d;
                res[ cr++ ] = data[i].i;
            }
        }
        if ( cr == n )
        {
            printf( "TAK\n" );
            for ( i = 0; i < cr; ++i )
            {
                printf( "%d ", res[i] );
            }
            printf( "\n" );
        }
        else printf("NIE\n");
    }
    else printf("NIE\n");
    free(data);
    free(res);
    return 0;
}