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

using namespace std;

vector<pair<pair<int,int>,int> > V1, V2;

int main()
{
    int n,z;
    scanf("%d%d",&n,&z);
    int d,a;
    for(int i=1;i<=n;++i)
    {
        scanf("%d%d",&d,&a);
        if (a>d)
            V1.push_back(make_pair(make_pair(d,a),i));
        else
            V2.push_back(make_pair(make_pair(a,d),i));

    }

    sort(V1.begin(), V1.end());
    sort(V2.begin(), V2.end());
    long long Z = z;
    for(int i=0;i<V1.size();++i)
    {
        Z -= V1[i].first.first;
        if (Z <= 0)
        {
            printf("NIE\n");
            return 0;
        }
        Z += V1[i].first.second;
    }
    for(int i=V2.size()-1;i>=0;--i)
    {
        Z -= V2[i].first.second;
        if (Z <= 0)
        {
            printf("NIE\n");
            return 0;
        }
        Z += V2[i].first.first;
    }

    printf("TAK\n");
    if (0 < V1.size())
        printf("%d",V1[0].second);

    for(int i=1;i<V1.size();++i)
        printf(" %d",V1[i].second);

    int st=0;
    if (0 == V1.size())
    {
        printf("%d",V2[V2.size()-1].second);
        st = 1;
    }

    for(int i=V2.size()-1-st;i>=0;--i)
        printf(" %d",V2[i].second);

    printf("\n");

    return 0;
}