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

using namespace std;

long long hp;
bool czy[100000];
int res[100000], n, a, b, p1, p2, pom1, pom2, j,l;
pair < pair < int, int> , int> plusz[100000], minusz[100000];
int main() {
	
	scanf("%d%lld", &n, &hp);
	
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &a, &b);
		b -= a;
		if (b >= 0) {
			plusz[p1] = make_pair(make_pair(a, b), i);
			p1++;
		} else {
			minusz[p2] = make_pair(make_pair(a, (-1)*b), i);
			p2++;
		}
	}
	
	sort(plusz, plusz + p1);
	
	for (int i = 0; i < p1; i++) {
		if (plusz[i].first.first >= hp) {
			printf("NIE");
			return 0;
		}
		hp += plusz[i].first.second;
		res[i] = plusz[i].second;
	}
	l = p1;
	sort(minusz, minusz + p2);
	
	for (int i = p2 - 1; i >= 0; i--) {
		if (czy[i] == 0) {
			if (hp - minusz[i].first.first <= 0) {
				printf("NIE");
				return 0;
			}
			if (i == 0) {
				res[l] = minusz[i].second;
				break;
			}
			if (hp - minusz[i].first.second > minusz[i-1].first.first) { 
				hp -= minusz[i].first.second;
				res[l] = minusz[i].second;
				czy[i] = 1;
				l++;
			} else {
				j = i - 1;
				while (hp - minusz[i].first.second <= minusz[j].first.first) {
					hp -= minusz[j].first.second;
					if (hp <= minusz[i].first.first) {
						printf("NIE");
						return 0;
					}
					res[l] = minusz[j].second;
					czy[j] = 1;
					l++;
					j--;
					if ( j < 0) {
						if (hp - minusz[i].first.first > 0)
							break;
						else {
							printf("NIE");
							return 0;
						}
					}
				}
				res[l] = minusz[i].second;
				hp -= minusz[i].first.second;
				czy[i] = 1;
				l++;
			}
		}
	}
	 
	 printf("TAK \n");
	 
	 for (int i = 0; i < n; i++)
		printf("%d ", res[i] + 1);
	return 0;
}