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

using namespace std;

struct Data
{
    int d,a,id;
};

int n,z;
vector< Data > inc_or_eq;
vector< Data > dec;

bool cmp1(const Data& a, const Data& b)
{
    return a.d < b.d;
}
bool cmp2(const Data& a, const Data& b)
{
    return a.a < b.a;
}

int main()
{
    scanf(" %d %d", &n, &z);
    for(int i=0; i<n; ++i)
    {
        Data data;
        data.id = i+1;
        scanf(" %d %d", &data.d, &data.a);
        if(data.d<=data.a)
            inc_or_eq.push_back(data);
        else
            dec.push_back(data);
    }

    sort(inc_or_eq.begin(),inc_or_eq.end(),cmp1);
    for(unsigned int i=0; i<inc_or_eq.size(); ++i)
    {
        if(z>inc_or_eq[i].d)
        {
            z-=inc_or_eq[i].d;
            z+=inc_or_eq[i].a;
        }
        else
        {
            printf("NIE");
            return 0;
        }
    }

    sort(dec.begin(),dec.end(),cmp2);
    int sub = 0;
    for(unsigned int i=0; i<dec.size(); ++i)
    {
        sub+=dec[i].d-dec[i].a;
    }
    z-=sub;
    if(z<=0)
    {
        printf("NIE");
        return 0;
    }
    for(unsigned int i=0; i<dec.size(); ++i)
    {
        if(z>dec[i].a)
        {
            z-=dec[i].a;
            z+=dec[i].d;
        }
        else
        {
            printf("NIE");
            return 0;
        }
    }

    printf("TAK\n");
    for(unsigned int i=0; i<inc_or_eq.size(); ++i)
    {
        if(dec.size()==0 && i==inc_or_eq.size()-1)
            printf("%d", inc_or_eq[i].id);
        else
            printf("%d ", inc_or_eq[i].id);
    }
    for(int i=dec.size()-1; i>=0; --i)
    {
        if(i==0)
            printf("%d", dec[i].id);
        else
            printf("%d ", dec[i].id);


    }

    return 0;
}