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
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;


struct Comparator {
	bool operator()(const pair<int, pair<int, int> >& p1, const pair<int, pair<int, int> >& p2)
	{
		return p1.second.first < p2.second.first;
	}
} comp_d;

struct Comparator_a {
	bool operator()(const pair<int, pair<int, int> >& p1, const pair<int, pair<int, int> >& p2)
	{
		return p1.second.second < p2.second.second;
	}
} comp_a;



int main()
{
	int n, z, d, a;
	int index = 1;
	vector< pair<int, pair<int, int>> > dodatnie;
	vector< pair<int, pair<int, int>> > ujemne;
	pair< int, pair<int, int>> p;
	vector<int> indeksy;

	scanf("%d %d", &n, &z);
	while(n--)
	{
		scanf("%d %d", &d, &a);
		//d obrazenia, a - zdrowie
		if(d <= a)
		{
			p = make_pair(index, make_pair(d, a));
			dodatnie.push_back(p);
		}
		else
		{
			p = make_pair(index, make_pair(d, a));
			ujemne.push_back(p);
		}
		index++;
	}

	stable_sort(dodatnie.begin(), dodatnie.end(), comp_d);
	stable_sort(dodatnie.begin(), dodatnie.end(), comp_a);
	int i;
	while(!dodatnie.empty())
	{
		i = dodatnie.size() - 1;	
		while(dodatnie[i].second.first >= z)
		{
			i--;
			if(i < 0)
			{
				printf("NIE\n");
				return 0;
			}
		}

		
		//cout << "Potwor: " << dodatnie[i].second.first << " " << dodatnie[i].second.second << endl;

		z -= dodatnie[i].second.first;
		z += dodatnie[i].second.second;
		//cout << "Aktualne zdrowie: " << z << endl;
		indeksy.push_back(dodatnie[i].first);
		dodatnie.erase(dodatnie.begin() + i);
		
	}

	stable_sort(ujemne.begin(), ujemne.end(), comp_d);
	stable_sort(ujemne.begin(), ujemne.end(), comp_a);

	while(!ujemne.empty())
	{
		i = ujemne.size() - 1;	
		while(ujemne[i].second.first >= z)
		{
			i--;
			if(i < 0)
			{
				printf("NIE\n");
				return 0;
			}
		}

		
		//cout << "Potwor: " << ujemne[i].second.first << " " << ujemne[i].second.second << endl;

		z -= ujemne[i].second.first;
		z += ujemne[i].second.second;
		//cout << "Aktualne zdrowie: " << z << endl;
		indeksy.push_back(ujemne[i].first);
		ujemne.erase(ujemne.begin() + i);
		
	}

	cout << "TAK\n";
	for(unsigned int i = 0; i < indeksy.size(); ++i)
	{
		cout << indeksy[i] << " ";
	}

	return 0;
}