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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <cstdio>
#include <iostream>
#include <set>
#include <algorithm>
#include <iomanip>

#define REP(i, n) for(int i = 0; i < n; i++)
#define FWD(i, a, b) for(int i = a; i < b; i++)
#define ALL(u) (u).begin(), (u).end()

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;

const int MAXN = 2010;

struct monster {
    LL req, delta, key;
    int ord;
};

bool por_req(monster a, monster b) {
    return a.req < b.req;
}

bool rev_por_key(monster a, monster b) {
    return a.key < b.key;
}

class Sol {
    int n;
    LL z, orig_z;

    public:

    void sol() {
        scanf("%d %lld", &n, &z);
        orig_z = z;
        REP(i, n) {
            LL req, delta;
            scanf("%lld %lld", &req, &delta);
            delta -= req;
            monsters.push_back(monster({req, delta, 0, i}));
        }
        if (not handle_pos_deltas()) {
            printf("NIE\n");
            return;
        }
        LL sum_delta = get_sum_delta();
        for (auto& mon : monsters) {
            mon.key = sum_delta - mon.delta - mon.req;
        }
        sort(monsters.begin(), monsters.end(), rev_por_key);
        order.insert(order.end(), monsters.begin(), monsters.end());
        if (check()) {
            printf("TAK\n");
            for (auto mon : order) {
                printf("%d ", mon.ord + 1);
            }
            printf("\n");
        } else {
            printf("NIE\n");
        }
    }

    bool check() {
        LL cur_z = orig_z;
        for (auto mon : order) {
            if (mon.req >= cur_z) {
                return false;
            }
            if (cur_z + mon.delta <= 0) {
                return false;
            }
            cur_z += mon.delta;
        }
        return true;
    }

    LL get_sum_delta() {
        LL sum = 0;
        for (auto mon : monsters) {
            sum += mon.delta;
        }
        return sum;
    }

    bool handle_pos_deltas() {
        sort(monsters.begin(), monsters.end(), por_req);
        vector<monster> remaining;
        for (auto mon : monsters) {
            if (mon.req < z and mon.delta >= 0) {
                order.push_back(mon);
                z += mon.delta;
            } else if (mon.req >= z) {
                return false;
            } else {
                remaining.push_back(mon);
            }
        }
        monsters = move(remaining);
        return true;
    }

    vector<monster> monsters, order;
};

int main() {
    Sol s;
    s.sol();
    return 0;
}