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
#include <stdio.h>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int n;
long long int z;
long long int obrazenia[100000];
long long int eliksir[100000];
vector < pair < long long int, pair < long long int, int > > > dodaj;
vector < pair < long long int, pair < long long int, int > > > odejmij;
int schemat[100000];
int poz_s = 0;
bool mozliwe = true;

int main()
{
	scanf("%d", &n);
	scanf("%lld", &z);
	
	for(int i = 0; i < n; i++)
	{
		scanf("%lld", &obrazenia[i]);
		scanf("%lld", &eliksir[i]);
		
		if(eliksir[i]-obrazenia[i] >= 0)
		{ dodaj.push_back(make_pair(obrazenia[i], make_pair(eliksir[i]-obrazenia[i], i))); }
		
		else odejmij.push_back(make_pair(eliksir[i], make_pair(obrazenia[i], i)));
	}
	
	sort(dodaj.begin(), dodaj.end());
	
	for(int i = 0; i < dodaj.size(); i++)
	{
		if(dodaj[i].first >= z) { mozliwe = false; break; }
		else { z += dodaj[i].second.first; schemat[poz_s] = dodaj[i].second.second; poz_s++; }
	}
	
	sort(odejmij.begin(), odejmij.end());
	
	for(int i = odejmij.size()-1; i >= 0; i--)
	{
		if(mozliwe == false) break;
		
		if(odejmij[i].second.first >= z) { mozliwe = false; break; }
		else
		{
			z -= odejmij[i].second.first;
			z += odejmij[i].first;
			if(z <= 0) { mozliwe = false; break; }
			else { schemat[poz_s] = odejmij[i].second.second; poz_s++; }
		}
	}
	
	if(mozliwe)
	{
		printf("TAK\n");
		for(int i = 0; i < n; i++) printf("%d ", schemat[i]+1);
		printf("\n");
	}
	
	else printf("NIE\n");
	
	return 0;
}