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

using namespace std;

struct Monster {
    int i;
    int d;
    int a;
    int lifeChange;
};

inline bool operator<(const Monster &a, const Monster &b) {
    return a.d < b.d;
}

vector<Monster> lifeUp, lifeUnchanged, lifeDown;
vector<int> order;

bool check(int z) {
    int life = z;
    for (int i=0; i<lifeUp.size(); i++) {
        if (life <= lifeUp[i].d) return false;
        life += lifeUp[i].lifeChange;
        order.push_back(lifeUp[i].i);
        //printf("lifeUp -> %d (%d %d %d)\n", life, lifeUp[i].i, lifeUp[i].d, lifeUp[i].a);
    }
    for (int i=0; i<lifeUnchanged.size(); i++) {
        if (life <= lifeUnchanged[i].d) return false;
        order.push_back(lifeUnchanged[i].i);
        //printf("lifeUnchanged (%d %d %d)\n", lifeUnchanged[i].i, lifeUnchanged[i].d, lifeUnchanged[i].a);
    }
    for (int i=lifeDown.size()-1; i>=0; i--) {
        if (life <= lifeDown[i].d) return false;
        life += lifeDown[i].lifeChange;
        order.push_back(lifeDown[i].i);
        //printf("lifeDown -> %d (%d %d %d)\n", life, lifeDown[i].i, lifeDown[i].d, lifeDown[i].a);
    }
    return true;
}

int main() {
    int n, z;
    scanf("%d%d", &n, &z);
    for (int i=1; i<=n; i++) {
        Monster m;
        m.i = i;
        scanf("%d%d", &m.d, &m.a);
        m.lifeChange = m.a - m.d;
        if (m.lifeChange < 0) lifeDown.push_back(m);
        else if (m.lifeChange > 0) lifeUp.push_back(m);
        else lifeUnchanged.push_back(m);
    }
    sort(lifeUp.begin(), lifeUp.end());
    sort(lifeDown.begin(), lifeDown.end());
    bool res = check(z);
    if (res) {
        printf("TAK\n");
        for (int i=0; i<order.size()-1; i++) printf("%d ", order[i]);
        printf("%d\n", order[order.size()-1]);
    }
    else printf("NIE\n");
    return 0;
}