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
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;



int n;
long long int S;
typedef pair<pair<int,int>,int> monster;
vector<monster> P;

char sgn(int x){ return x<0?-1:(x==0?0:1); }
bool cmp(monster m1, monster m2){
    int a1=m1.first.first, b1=m1.first.second;
    int a2=m2.first.first, b2=m2.first.second;
    if (b1-a1==0 && b2-a2==0) return m1<m2;
    if (b1-a1>0 && b2-a2>0) return m1<m2;
    if (b1-a1<0 && b2-a2<0) return m1>m2;
    return sgn(b1-a1)>sgn(b2-a2);
}

int main(){

    // Wczytywanie danych
    scanf("%d %lld", &n, &S);
    P.resize(n);
    for(int i=0; i<n; ++i){
        scanf("%d %d", &P[i].first.first, &P[i].first.second);
        P[i].second = i + 1;
    }

    // Sortowanie potworow
    sort(P.begin(), P.end(), cmp);

    // Algorytm
    bool ok = true;
    queue<pair<pair<int,int>, int> > Q;
    int first_u = n;
    vector<int> rest;

    for(int i=0; i<n && ok; ++i){
        int a=P[i].first.first, b=P[i].first.second;
        if (b-a<0){
            if (first_u==n) first_u=i;
            while(!Q.empty()){
                int aa=Q.front().first.first, bb=Q.front().first.second;
                if (S+bb-aa<P[i].first.first) break;
                else {
                    rest.push_back(Q.front().second);
                    Q.pop();
                    S = S-a+b;
                }
            }
            if (i!=n-1 && S+b-a<P[i+1].first.first) Q.push(make_pair(make_pair(a,b), P[i].second));
            else { S -= a; ok = ok && (S>0); S += b; rest.push_back(P[i].second); }
        } else { S -= a; ok = ok && (S>0); S += b; }
    }
    ok = ok && Q.empty();

    if (!ok) printf("NIE\n");
    else {
        printf("TAK\n");
        for(int i=0; i<first_u; ++i) printf("%d ", P[i].second);
        for(int i=0; i<rest.size(); ++i) printf("%d ", rest[i]);
        printf("\n");
    }

}