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
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct tNaPlus {
  long id;
  long strata, zysk;
  bool operator<(const tNaPlus &rhs) const {
    return strata < rhs.strata;
  }
};

struct tNaMinus {
  long id;
  long strata, zysk;
  bool operator<(const tNaMinus &rhs) const {
    return zysk < rhs.zysk;
  }
};

int main() {
  ios_base::sync_with_stdio(0);

  long n, z;
  long d, a;
  vector<tNaPlus> vNaPlus;
  vector<tNaPlus> vNaZero;
  vector<tNaMinus> vNaMinus;
  tNaPlus naPlus;
  tNaMinus naMinus;
  long long poziomPoPlusie;
  long long aktPocz, aktKonc;

  cin >> n >> z;
  for(long i = 0; i < n; ++i) {
    cin >> d >> a;
    if(d <= a) {
      naPlus.id = i + 1;
      naPlus.strata = d;
      naPlus.zysk = a;
      if(a == d)
         vNaZero.push_back(naPlus);
      else
        vNaPlus.push_back(naPlus);
    } else {
      naMinus.id = i + 1;
      naMinus.strata = d;
      naMinus.zysk = a;
      vNaMinus.push_back(naMinus);
    }
  }
  sort(vNaPlus.begin(), vNaPlus.end());
  sort(vNaZero.begin(), vNaZero.end());
  sort(vNaMinus.begin(), vNaMinus.end());
/*
  cout << "naPlus" << endl;
  for(vector<tNaPlus>::iterator it = vNaPlus.begin(); it != vNaPlus.end(); ++it)
    cout << it->id << " " << it->strata << " " << it->zysk << endl;
  cout << "naZero" << endl;
  for(vector<tNaPlus>::iterator it = vNaZero.begin(); it != vNaZero.end(); ++it)
    cout << it->id << " " << it->strata << " " << it->zysk << endl;
  cout << "naMinus" << endl;
  for(vector<tNaMinus>::iterator it = vNaMinus.begin(); it != vNaMinus.end(); ++it)
      cout << it->id << " " << it->strata << " " << it->zysk << endl;
*/
  poziomPoPlusie = z;
  for(vector<tNaPlus>::iterator it = vNaPlus.begin(); it != vNaPlus.end(); ++it)
    if(it->strata < poziomPoPlusie)
      poziomPoPlusie += it->zysk - it->strata;
    else {
      cout << "NIE" << endl;
      return 0;
    }
  for(vector<tNaPlus>::iterator it = vNaZero.begin(); it != vNaZero.end(); ++it)
    if(it->strata >= poziomPoPlusie) {
      cout << "NIE" << endl;
      return 0;
    }
  aktPocz = -1; aktKonc = -1;
  for(vector<tNaMinus>::iterator it = vNaMinus.begin(); it != vNaMinus.end(); ++it)
    if(it->zysk < aktKonc) {
      aktPocz = aktKonc;
      aktKonc = aktPocz + it->strata - it->zysk;
    } else {
      aktPocz = it->zysk;
      aktKonc = it->strata;
    }
  if(aktKonc < poziomPoPlusie) {
    cout << "TAK" << endl;
    for(vector<tNaPlus>::iterator it = vNaPlus.begin(); it != vNaPlus.end(); ++it)
      cout << it->id << " ";
    for(vector<tNaPlus>::iterator it = vNaZero.begin(); it != vNaZero.end(); ++it)
      cout << it->id << " ";
    for(vector<tNaMinus>::reverse_iterator it = vNaMinus.rbegin(); it != vNaMinus.rend(); ++it)
      cout << it->id << " ";
  } else
    cout << "NIE" << endl;
  return 0;
}