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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct monster {
    int dmg;
    int heal;
    int index;
    monster(){}
    monster(int dmg, int heal) : dmg(dmg), heal(heal) {}
};
struct nettoMonster {
    int dif;
    monster other;
    nettoMonster(){}
    nettoMonster(int dif, monster other) : dif(dif), other(other) {}
};
inline bool operator<( const monster& lhs, const monster& rhs ) {
    return lhs.dmg == rhs.dmg ? lhs.heal == rhs.heal ? lhs.index < rhs.index : lhs.heal < rhs.heal : lhs.dmg < rhs.dmg;
}
inline bool operator<( const nettoMonster& lhs, const nettoMonster& rhs ) {
    return lhs.dif == rhs.dif ? rhs.other < lhs.other : lhs.dif < rhs.dif;
}
int main() {
    int n, hp;
    scanf("%d%d",&n,&hp);
    vector<monster> healers;
    multiset<monster> monsters;
    multiset<nettoMonster> netto;
    for(int i = 0; i < n; i++) {
        monster m;
        scanf("%d%d",&m.dmg, &m.heal);
        m.index = i + 1;
        if(m.heal >= m.dmg)
            healers.push_back(m);
        else {
            monsters.insert(m);
            netto.insert(nettoMonster(m.dmg - m.heal, m));
        }
    }
    sort(healers.begin(), healers.end());
    vector<int> result;
    bool fail = false;
    for(int i = 0; i < healers.size(); i++) {
        if(hp > healers[i].dmg) {
            hp -= healers[i].dmg;
            hp += healers[i].heal;
            result.push_back(healers[i].index);
        } else {
            fail = true;
            break;
        }
    }
    if(fail) {
        printf("NIE\n");
        return 0;
    }
    while(!monsters.empty()) {
        if(monsters.size() == 1) {
            if(monsters.begin()->dmg < hp) {
                result.push_back(monsters.begin()->index);
                monsters.clear();
                break;
            } else {
                printf("NIE\n");
                return 0;
            }
        }
        set<monster>::reverse_iterator wtf = monsters.rbegin();
        wtf++;
        if(hp - monsters.rbegin()->dmg + monsters.rbegin()->heal > wtf->dmg) {
            result.push_back(monsters.rbegin()->index);
            hp -= monsters.rbegin()->dmg;
            hp += monsters.rbegin()->heal;
            netto.erase(nettoMonster(monsters.rbegin()->dmg - monsters.rbegin()->heal, *monsters.rbegin()));
            monsters.erase(*monsters.rbegin());
        } else {
            if(hp - netto.begin()->dif > monsters.rbegin()->dmg) {
                hp -= netto.begin()->dif;
                result.push_back(netto.begin()->other.index);
                monsters.erase(netto.begin()->other);
                netto.erase(*netto.begin());
            } else {
                printf("NIE\n");
                return 0;
            }
        }
    }
    printf("TAK\n");
    for(int i = 0; i < result.size(); i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    return 0;
}