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
#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#define MAXN 100005
typedef long long int LL; 
using namespace std;

int n,a,b;
int Res[MAXN];

struct monster {
	int a,b,i,d;
	monster(int a,int b,int i) : a(a), b(b), i(i+1) {}
};

struct profit_comparator {
	bool operator () (const monster &m1,const monster &m2) const {
		return (m1.a == m2.a && m1.b > m2.b) || m1.a < m2.a;
	}
};

struct attack_comparator {
	bool operator () (const monster &m1,const monster &m2) const {
		if(m1.a == m2.a) {
			if(m1.b == m2.b) return m1.i < m2.i;
			return m1.b > m2.b;
		}
		return m1.a > m2.a;
	}
};

struct potion_comparator {
    bool operator () (const monster &m1,const monster &m2) const {
		if(m1.b == m2.b) {
			if(m1.a == m2.a) return m1.i < m2.i;
			return m1.a > m2.a;
		}
		return m1.b > m2.b;
    }
};

bool fun1(LL &health, vector<monster> &V) {
	profit_comparator comparator;
	sort(V.begin(), V.end(), comparator);
	
	for(int i=0;i<V.size();i++) {
		if(health <= V[i].a) return false;
		health += V[i].b - V[i].a;
		Res[i] = V[i].i;
	}
	return true;
}

bool fun2(LL &health, set<monster,attack_comparator> &A) {

	set<monster,potion_comparator> D(A.begin(), A.end());
	
	while(A.size()) {
		const monster &mD = *(D.begin());
		const monster &mA = *(A.begin());
		
		if(health > mD.a - mD.b + mA.a) {
			health += mD.b - mD.a;
			Res[n-A.size()] = mD.i;
			A.erase(*(D.begin()));
			D.erase(D.begin());
		}
		else if(health > mA.a) {
			health += mA.b - mA.a;
			Res[n-A.size()] = mA.i;
			D.erase(*(A.begin()));
			A.erase(A.begin());
		}
		else return false;
	}
	return true;
}


int main() 
{
	LL health;
	set<monster,attack_comparator> S;
	vector<monster> V;
	
	scanf("%d %lld",&n,&health);
	
	for(int i=0;i<n;i++) {
		scanf("%d %d",&a,&b);
		if(a > b) S.insert(monster(a,b,i));
		else V.push_back(monster(a,b,i));
	}
	
	if(fun1(health, V) && fun2(health, S)) {
		printf("TAK\n");
		for(int i=0;i<n;i++) printf("%d ",Res[i]);
		printf("\n");
	}
	else printf("NIE\n");
	return 0;
}