boh.cc

#include <iostream>
#include <queue>
#include <algorithm>
#define MAXN 100005

using namespace std;

typedef pair<int, int> pii;
typedef priority_queue<pii> prique;
pii M[MAXN];
int A[MAXN], sz, z;
int id1[MAXN], id2[MAXN];

bool solve(int id[], int n) {
  int j;
  for (int i = 0; i < n; ++i) {
    j = id[i];
    z -= M[j].first;
    if (z <= 0)
      return false;
    z += M[j].second;
    A[sz++] = j;
  }
  return true;
}

int main() {
  std::ios::sync_with_stdio(false);
  int n, d, a, sz1 = 0, sz2 = 0;
  cin >> n >> z;
  for (int i = 0; i < n; ++i) {
    cin >> d >> a;
    M[i] = pii(d, a);
    if (a > d)
      id1[sz1++] = i;
    else
      id2[sz2++] = i;
  }
  sort(id1, id1+sz1, [](int i, int j) {return M[i].first < M[j].first;});
  sort(id2, id2+sz2, [](int i, int j) {return M[i].second > M[j].second;});
  bool valid = solve(id1, sz1);
  if (valid)
    valid = solve(id2, sz2);
  if (valid) {
    cout << "TAK" << endl;
    cout << A[0] + 1;
    for (int i = 1; i < n; ++i)
      cout << ' ' << A[i] + 1;
    cout << endl;
  } else {
    cout << "NIE" << endl;
  }
}