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
114
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;

class WalkaDobra {
    public:
        long obrazenia;
        long elixir;
        long nrPotwora;

        WalkaDobra(long o = 0 , long e = 0 , long nr = 0 ) : obrazenia(o), elixir(e), nrPotwora(nr) {}

        void print() const {
            printf("(ob=%ld, elix=%ld, nrPot = %ld\n", obrazenia, elixir, nrPotwora);
        }

        bool operator < (const WalkaDobra &other) const {
            if (this->obrazenia < other.obrazenia)
                return true;
            if (this->obrazenia == other.obrazenia)
                return this->elixir > other.elixir;
            return false;
        }
};

class WalkaZla {
    public:
        long obrazenia;
        long elixir;
        long nrPotwora;
        WalkaZla(long o = 0, long e = 0, long nr = 0) : obrazenia(o), elixir(e), nrPotwora(nr) {}

        void print() const {
            printf("(ob=%ld, elix=%ld, nrPot = %ld\n", obrazenia, elixir, nrPotwora);
        }

        bool operator < (const WalkaZla &other) const {
            if (this->obrazenia < other.obrazenia)
                return false;
            if (this->obrazenia == other.obrazenia)
                return this->elixir > other.elixir;
            return true;
        }
};

int main() {
    LL zycie;
    long ile;
    vector <WalkaDobra> warto;
    vector <WalkaZla> nieWarto;

    scanf("%ld %lld", &ile, &zycie);

    vector<long> odpowiedz(ile);
    int odpPoz = 0;

    for (long i = 1; i <= ile; ++i) {
       long ob, elix; 
       scanf("%ld %ld", &ob, &elix); 

       if (elix > ob) {
            WalkaDobra w = WalkaDobra(ob, elix, i);
            warto.push_back(w);
       } else {
            WalkaZla w = WalkaZla(ob, elix, i);
            nieWarto.push_back(w);
       }

    }
       sort(warto.begin(), warto.end());
       sort(nieWarto.begin(), nieWarto.end());

//        printf("warto\n");
//       for (vector<WalkaDobra>::iterator it = warto.begin(); it != warto.end(); ++it)
//        it->print();
//
//        printf("nie warto\n");
//       for (vector<WalkaZla>::iterator it = nieWarto.begin(); it != nieWarto.end(); ++it)
//        it->print();

       for (vector<WalkaDobra>::iterator it = warto.begin(); it != warto.end(); ++it) {
            zycie -= it->obrazenia;
            if (zycie <= 0)
                break;
            zycie += it->elixir;
            odpowiedz[odpPoz] = it->nrPotwora;
            ++odpPoz;
       }

       if (zycie > 0) {
           for (vector<WalkaZla>::iterator it = nieWarto.begin(); it != nieWarto.end(); ++it) {
               zycie -= it->obrazenia;
               if (zycie <= 0)
                   break;
               zycie += it->elixir;
               odpowiedz[odpPoz] = it->nrPotwora;
               ++odpPoz;
           }

       }

        if (zycie > 0) {
            printf("TAK\n");
            for (vector<long>::iterator it = odpowiedz.begin(); it != odpowiedz.end(); ++it) {
                printf("%ld ", *it);
            }
        } else {
            printf("NIE\n");
        }

    return 0;
}