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
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

struct monster {
    int cost;
    int heal;
    int index;
};

bool compare_by_cost(monster first, monster second) {
    return first.cost < second.cost;
}

bool compare_by_heal_reversed(monster first, monster second) {
    return first.heal > second.heal;
}

int main() {

    int n;
    long long z;
    vector<monster> positive;
    vector<monster> negative;

    scanf("%d %lld", &n, &z);

    for(int i = 1 ; i <= n ; ++i) {
       monster m;
       scanf("%d %d", &m.cost, &m.heal);
       m.index = i;
       if(m.heal > m.cost) {
            positive.push_back(m);
       } else {
            negative.push_back(m);
       }
    }

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

    for(int i = 0 ; i < positive.size(); ++i) {
        int cost = positive[i].cost;
        int heal = positive[i].heal;

        if(cost >= z) {
            printf("NIE\n");
            return 0;
        }

        z = z - cost + heal;
    }

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

    for(int i = 0 ; i < negative.size(); ++i) {
        int cost = negative[i].cost;
        int heal = negative[i].heal;
        
        if(cost >= z) {
            printf("NIE\n");
            return 0;
        }

        z = z - cost + heal;
    }
   
    printf("TAK\n");
    for(int i = 0 ; i < positive.size(); ++i) {
        printf("%d ", positive[i].index);
    }
    
    for(int i = 0 ; i < negative.size(); ++i) {
        printf("%d ", negative[i].index);
    }

    printf("\n");

    return 0;
}