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
#include <stdio.h>
#include <stdlib.h>
int poz = 0;
long long int z;

struct w {
  int k; //koszt
  int p; //przychod
  int poz;
  int next;
  int prev;
};
struct w *in;

int f(const void* A, const void* B) {
  //printf("A.p %d B.p %d\n", ((struct w*)A)->p, ((struct w*)B)->p);
  if(((struct w*)A)->p > 0 && ((struct w*)B)->p > 0) {
		//printf("1\n");
		if(((struct w*)A)->p > ((struct w*)B)->p) return -1;
	  else if(((struct w*)A)->p < ((struct w*)B)->p) return 1;
	  else return 0;
	} else {
		//printf("2\n");
		if(((struct w*)A)->p+((struct w*)A)->k > ((struct w*)B)->p+((struct w*)B)->k) return -1;
	  else if(((struct w*)A)->p+((struct w*)A)->k < ((struct w*)B)->p+((struct w*)B)->k) return 1;
	  else return 0;
	}
}

void find_up() {
	while(poz != 0) {
    if((*(in+poz)).prev == -1) break;
		if((*(in+(*(in+poz)).prev)).k >= z) break;
		poz = (*(in+poz)).prev;
  }
}

void find_down() {
	poz = (*(in+poz)).next;
	while(poz != -1) {
    if((*(in+poz)).k<z) break;
	  poz = (*(in+poz)).next;
	}
}

void update() {
  int q = 0;
  if((*(in+poz)).next != -1) {
		(*(in+(*(in+poz)).next)).prev = (*(in+poz)).prev;
    q = 1;
	}
	if((*(in+poz)).prev != -1) {
		(*(in+(*(in+poz)).prev)).next = (*(in+poz)).next;
    if(q != 1) q = 2;
  }
  z += (*(in+poz)).p;
  //printf("z %lld\n", z);
  if(q == 1) 
		poz = (*(in+poz)).next;
  else if(q == 2)
		poz = (*(in+poz)).prev;
  //printf("poz %d\n", poz);
}

int main() {
  int *d;
  int n,i,k,p;
  scanf("%d %lld\n", &n, &z);
  in = (struct w*)malloc(sizeof(struct w)*n);
  d = (int*)malloc(sizeof(int)*n);
  i=0;
  while(i<n) {
    scanf("%d %d\n", &k, &p);
    (*(in+i)).k = k;
    (*(in+i)).p = p-k;
    (*(in+i)).poz = i+1;
    i++;
  }
  qsort(in, n, sizeof(struct w), f);
	i=0;
  while(i<n) {
    (*(in+i)).next = i+1;
    (*(in+i)).prev = i-1;
    i++;
  }
  (*(in+n-1)).next = -1;
  i = 0;
  poz = 0;
  while(i<n && z > 0) {
    if((*(in+poz)).k >= z) {
//			printf("szukam w dol\n");
			find_down();
      if(poz == -1) {
				break;
			}
		} else {
//			printf("szukam w gore\n");
			find_up();
		}
		*(d+i) = (*(in+poz)).poz;
		update();
		i++;
  }
  if(i == n) {
		printf("TAK\n");
    i=0;
    while(i<n) {
			printf("%d ", *(d+i));
			i++;
    }
	} else
		printf("NIE");
/*
  i = 0;
  while(i<n) {
    printf("%d\n", (*(in+i)).p);
    i++;
  }*/
	return 0;
}