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
#include <algorithm>
#include <cstdio>
#include <vector>

int main() {
	int n, z;
	scanf("%d%d", &n, &z);
	std::vector<std::pair<int, std::pair<int, int> > > dodatnie, ujemne;
	for(int i = 0; i < n; i++) {
		int d, a;
		scanf("%d%d", &d, &a);
		if(a-d >= 0)
			dodatnie.push_back(std::make_pair(d, std::make_pair(-(a-d), i+1)));
		else
			ujemne.push_back(std::make_pair(-a, std::make_pair(d, i+1)));
	}
	std::sort(dodatnie.begin(), dodatnie.end());
	std::sort(ujemne.begin(), ujemne.end());
	std::vector<int> visits;
	for(int i = 0; i < dodatnie.size(); i++) {
		visits.push_back(dodatnie[i].second.second);
		if(dodatnie[i].first < z)
			z -= dodatnie[i].second.first;
		else {
			printf("NIE\n");
			return 0;
		}
	}
	for(int i = 0; i < ujemne.size(); i++) {
		//printf("odwiedzam %d\n", ujemne[i].second.second);
		visits.push_back(ujemne[i].second.second);
		if(ujemne[i].second.first < z) {
			//printf("przed %d\n", z);
			z -= ujemne[i].second.first;
			//printf("po ataku %d\n", z);
			z -= ujemne[i].first;
			//printf("po leczeniu %d\n", z);
		}
		else {
			printf("NIE\n");
			return 0;
		}
	}
	printf("TAK\n");
	for(int i = 0; i < visits.size(); i++)
		printf("%d ", visits[i]);
	return 0;
}