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
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <stdio.h>
#include <stdlib.h>

typedef struct _data {
	int num, val, dif;
	struct _data *next, *prev;
} t_data;

t_data inc[100000];
t_data dec[100000];
t_data *dec_top;
int incc, decc;

int result[100000];
int resultc;

int cmpinc (const void *a, const void *b)
{
	if(((t_data*)a)->val <  ((t_data*)b)->val)
		return -1;
	if(((t_data*)a)->val >  ((t_data*)b)->val)
		return 1;
	return 0;
}

int cmpdec (const void *a, const void *b)
{
	if(((t_data*)a)->val+((t_data*)a)->dif >  ((t_data*)b)->val+((t_data*)b)->dif)
		return -1;
	if(((t_data*)a)->val+((t_data*)a)->dif <  ((t_data*)b)->val+((t_data*)b)->dif)
		return 1;

	return 0;
}

int put(t_data *da, long long int z) {
	int res;
	if(da && z > da->val) {
		res = 1;
		result[resultc++] = da->num;
	} else {
		res = 0;
	}
	return res;
}

int main() {
	int n, d, a, i, res;
	long long int z;
	long long int sum;
	t_data *da;
	
	incc = decc = 0;
	scanf("%d %lld", &n, &z);
	sum = z;
	for(i=0; i<n; i++) {
		scanf("%d %d", &d, &a);
		if(d > a) {
			(dec+decc)->num = i+1;
			(dec+decc)->val = d;
			(dec+decc)->dif = a-d;
			sum += (dec+decc)->dif;
			decc++;
		} else {
			(inc+incc)->num = i+1;
			(inc+incc)->val = d;
			(inc+incc)->dif = a-d;
			sum += (inc+incc)->dif;
			incc++;
		}
	}
	if(sum > 0) {
		res = 1;
		qsort(inc, incc, sizeof(t_data), cmpinc);
		qsort(dec, decc, sizeof(t_data), cmpdec);

		for(i=0; res && i<incc; i++) {
			if((inc+i)->val < z) {
				z += (inc+i)->dif;
			} else {
				res = 0;
			}
		}
		
		dec_top = dec;
		for(i=0; i<decc; i++) {
			(dec+i)->prev = (dec+i-1);
			(dec+i)->next = (dec+i+1);
		}
		(dec+0)->prev = NULL;
		(dec+decc-1)->next = NULL;
		
		da = dec_top;
		
		resultc = 0;
		while(res && da) {
			i = put(da, z);
			if(!i)
				res = 0;
			else {
				while(i--) {
					z += da->dif;
					da = da->next;
				}
			}
		}

		printf("%s\n", "NIE\0TAK"+(res<<2));
		if(res) {
			for(i=0; i<incc; i++) {
				printf("%d ", (inc+i)->num);
			}
			for(i=0; i<decc; i++) {
				printf("%d ", *(result+i));
			}
/*			for(da=dec_top; da; da=da->next) {
				printf("%d ", da->num);
			}
*/
			printf("\n");
		}
	} else {
		printf("NIE\n");
	}
	
	return 0;
}