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
#include <cstdio>
#include <algorithm>
using namespace std;

#define LL long long

#define MAX_N 100000

int n;
LL z;

struct int2
{
    int a,d,i;
};

int2 T1[MAX_N];
int T1Size=0;
int2 T[MAX_N];
int TSize=0;
int W[MAX_N];
int WSize=0;

bool op1(int2 a,int2 b)
{
    return a.d<b.d;
}

bool op2(int2 a,int2 b)
{
    return a.d>b.d;
}

int main()
{
    scanf("%d%lld",&n,&z);
    for(int a=0;a<n;++a)
    {
        int2 i;
        i.i=a+1;
        scanf("%d%d",&i.d,&i.a);
        if(i.a>=i.d)T1[T1Size++]=i;
        else T[TSize++]=i;
    }
    sort(T1,T1+T1Size,op1);
    for(int a=0;a<T1Size;++a)
    {
        if(z<=T1[a].d)
        {
            printf("NIE");
            return 0;
        }
        z+=T1[a].a-T1[a].d;
        W[WSize++]=T1[a].i;
    }
    sort(T,T+TSize,op2);
    for(int a=0;a<TSize;)
    {
        if(z<=T[a].d)
        {
            printf("NIE");
            return 0;
        }
        int b=a;
        for(++a;a<TSize && z+T[a].a-T[a].d>T[b].d;++a)
        {
            z+=T[a].a-T[a].d;
            W[WSize++]=T[a].i;
        }
        z+=T[b].a-T[b].d;
        W[WSize++]=T[b].i;
    }
    printf("TAK\n");
    for(int a=0;a<WSize;++a)
    {
        printf("%d ",W[a]);
    }
    return 0;
}