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
// Author: Adam Krasuski

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct enemy{
    int number;
    int needed_life;
    int net_worth;
};

int cmp_pos(enemy e1,enemy e2){
    return e1.needed_life<e2.needed_life;
}

int cmp_neg(enemy e1,enemy e2){
    return (e1.needed_life+e1.net_worth)>(e2.needed_life+e2.net_worth);
}

int main(){
    int n,z;
    scanf("%d %d",&n,&z);
    vector<enemy>positive,negative;//contain those with positive or negative net_worth
    for(int i=0;i<n;i++){
        int d,a;
        scanf("%d %d",&d,&a);
        int nw=a-d;
        enemy en={i+1,d,nw};
        if(nw<0){
            negative.push_back(en);
        }
        else{
            positive.push_back(en);
        }
    }
    sort(positive.begin(),positive.end(),cmp_pos);
    sort(negative.begin(),negative.end(),cmp_neg);
    long long int health=z;
    int ok=1;
    for(int i=0;i<positive.size();i++){
        if(health>positive[i].needed_life){
            health+=positive[i].net_worth;
        }
        else{
            ok=0;
        }
        //printf("Positive enemy: %d %d, health: %d\n",positive[i].needed_life,positive[i].net_worth,health);
    }
    for(int i=0;i<negative.size();i++){
        if(health>negative[i].needed_life){
            health+=negative[i].net_worth;
        }
        else{
            ok=0;
        }
        //printf("Negative enemy: %d %d sum:%d, health:%d\n",
        //       negative[i].needed_life,negative[i].net_worth,negative[i].needed_life+negative[i].net_worth,health);
    }
    if(!ok){
        printf("NIE\n");
    }
    else{
        printf("TAK\n");
        for(int i=0;i<positive.size();i++){
            printf("%d ",positive[i].number);
        }
        for(int i=0;i<negative.size();i++){
            printf("%d ",negative[i].number);
        }
    }

}