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
#include <iostream>

struct dane{
	long int d,a,kt;
	double wynik;
};


int partition(dane tablica[], int p, int r) 
{
	double x = tablica[p].wynik;
	int i = p, j = r; 
	while (true)
	{
		while (tablica[j].wynik > x) 
			j--;
		while (tablica[i].wynik < x) 
			i++;
		if (i < j) 
		{
			std::swap(tablica[i].d, tablica[j].d);
			std::swap(tablica[i].wynik, tablica[j].wynik);
			std::swap(tablica[i].a, tablica[j].a);
			std::swap(tablica[i].kt, tablica[j].kt);
			i++;
			j--;
		}
		else 
			return j;
	}
}
 
void quicksort(dane tablica[], int p, int r) 
{
int q;
if (p < r)
{  
q = partition(tablica,p,r);
quicksort(tablica, p, q); 
quicksort(tablica, q+1, r);
}
}                  


int main()
{	
	unsigned long int n, i;
	long int z;
	std::cin >> n >> z;
	struct dane *test = new struct dane[n];
	for(i = 0;i<n;i++)
	{		
		std::cin >> test[i].d >> test[i].a;
		if(test[i].d!=0)
			test[i].wynik=(double(test[i].a)/double(test[i].d));
		else
			test[i].wynik=(double(test[i].a))+1;
		test[i].kt=i+1;
	}
	bool tester;
	quicksort(test, 0, n-1);
	for(i = n-1;i >= 0;i--)
	{
		tester = true;
		if((z-test[i].d)<1)
		{			
			unsigned long int k=i;
			while((z-test[k].d)<1)
			{
				if (k==0)
				{
				 printf("NIE");
				 tester = false;
				 break;
				}
				k=k-1;
				if((z-test[k].d<1)&&(k==0))
				{
					printf("NIE");
					tester = false;
					break;
				}
				if(z-test[k].d>0)
				{
					std::swap(test[i].d, test[k].d);
					std::swap(test[i].wynik, test[k].wynik);
					std::swap(test[i].a, test[k].a);
					std::swap(test[i].kt, test[k].kt);
					break;
				}			
			}
		}
		if(tester==false)
			break;
		z=z-test[i].d;
		z=z+test[i].a;
		if(i==0)
			break;
	}
	if(tester)
	{
		std::cout<<"TAK\n";
		for(i = n-1;i >=0;i--)
		{
			std::cout<<test[i].kt<<" ";
			if(i==0)
			 break;
		}			
	}
	delete []test;	
	return 0;
}