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
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
struct dane{
	int i,ob,zd;
	void add(int i1, int ob1, int zd1){
		i=i1; ob=ob1; zd=zd1;
		}
}DoD[100009],UjE[100009];

int n,pom,z0,i,d,u,i_d,i_u,wyn[100009],od[100009], DANE[10009][2];
bool sor_dod(dane A,dane B){
	if(A.ob<B.ob)return 1;
	return 0;
}
bool sor_uje(dane A,dane B){
	if(A.ob>B.ob)return 1;
	return 0;
}

int main(){
	scanf("%d%d",&n,&z0);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&u,&d);
		DANE[i][0]=u;
		DANE[i][1]=d;
		if(u<=d){
			DoD[i_d].add(i,u,d);
			i_d++;
		}else{
			UjE[i_u].add(i,u,d);
			
			i_u++;
		}}
	sort(DoD,DoD+i_d,sor_dod);
	sort(UjE,UjE+i_u,sor_uje);
	UjE[i_u].ob=0;
	long long zdrowie=z0;
	int i=0,ok=1;
	for(;i<i_d&&ok;i++){
		if(zdrowie<=DoD[i].ob){
			ok=0;
		}
		zdrowie+=DoD[i].zd-DoD[i].ob;
		wyn[i]=DoD[i].i;
	}
stack<int> S;
int pom2,i_wyn=i_d,ok2;
long long zdrowie2=zdrowie;
UjE[i_u].ob=0;	
UjE[i_u+1].ob=0;	
od[0]=1;
//UJEMNE
		while(i<n&&ok){
			if(od[i]==0)S.push(i); else i++;
			od[i]=1;
			while(!S.empty()&&ok&&i_wyn<n){
				pom=S.top();
				pom2=zdrowie-UjE[i-i_d].ob+UjE[i-i_d].zd;
				if(zdrowie<=UjE[i-i_d].ob)ok=0;
				 ok2=1;
				while(UjE[i-i_d+1].ob>=pom2&&ok){
					ok2=0;
					if(UjE[i-i_d+1].ob>=zdrowie)ok=0;
					if(i-i_d>=i_u)ok=0;
					if(od[i]==0)S.push(i);
					od[i]=1;
					i++;}
				if(ok){
					wyn[i_wyn]=UjE[i-i_d].i;
					i_wyn++;
					zdrowie+=UjE[i-i_d].zd-UjE[i-i_d].ob;
					if(zdrowie<=0)ok=0;
					S.pop();
				}}
				i++;
			}
while(!S.empty()){
		wyn[i_wyn]=UjE[S.top()-i_d].i;
		S.pop();
	}
	ok=1;
long long qw=z0;
for(int i=0;i<n&&ok;i++){
	qw-=DANE[wyn[i]][0];
	if(qw<=0)ok=0;
	qw+=DANE[wyn[i]][1];
}	
	if(ok)printf("TAK\n"); else {printf("NIE\n"); return 0;}
	for(int i=0;i<n;i++)printf("%d ",wyn[i]);
	printf("\n");
			
return 0;
}