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
#include <cstdio>
#include <set>
#include <list>
using namespace std;

struct Event {
    int profit;
    int req; /// life required to take a profit
    int id;
    Event () {}
    Event (int _profit, int _req, int _id)
        : profit(_profit), req(_req), id(_id) {}
};

struct Gains_cmp {
    bool operator() (const Event &a, const Event &b){
        // Sorting by req. Every profit pays off.
        if (a.req < b.req) return true;
        if (a.req > b.req) return false;
        return (a.id < b.id);
    }
};

bool Losses_cmp (const Event &a, const Event &b){
    if (a.req < b.req) return false;
    if (a.req > b.req) return true;
    return (a.profit > b.profit);
}


list<int> Result;
multiset<Event, Gains_cmp> Gains;
list<Event> Losses;

bool the_game ()
{
    int n, d, a;
    long long z;
    Event ev;
    scanf ("%d%lld", &n, &z);
    for (int i = 0; i < n; i++){
        scanf ("%d%d", &d, &a);
        if (d <= a)
            // profit
            Gains.insert (Event (a - d, d, i + 1));
        else
            // waste
            Losses.push_back (Event (a - d, d, i + 1));
    }

    /// Get a life!
    multiset<Event, Gains_cmp>::iterator git;
    while (!Gains.empty ()){
        git = Gains.lower_bound (Event (z, 0, 0));
        if (git == Gains.end ())
            return false; // DEFEAT
        ev = *git;
        Gains.erase (git);
        //printf ("GAINS Life = %lld : %d | %d | %d\n", z, ev.req, ev.profit, ev.id);
        z += static_cast<long long> (ev.profit);
        Result.push_back (ev.id);
    }

    /// No play, no game :)
    Losses.sort (Losses_cmp);
    for (list<Event>::iterator lit = Losses.begin (); lit != Losses.end (); lit++){
        ev = *lit;
        //printf ("LOSSES Life = %lld : %d | %d | %d\n", z, ev.req, ev.profit, ev.id);
        if (z <= ev.req)
            return false; // DEFEAT
        z += static_cast<long long> (ev.profit);
    }

    return true; // VICTORY
}


int main ()
{
    if (the_game ())
    {
        printf ("TAK\n");
        for (list<int>::iterator it = Result.begin (); it != Result.end (); it++)
            printf ("%d ", *it);
        for (list<Event>::iterator it = Losses.begin (); it != Losses.end (); it++)
            printf ("%d ", it->id);
        printf ("\n");
    } else
        printf ("NIE\n");
}