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

struct P
{
	P(int d, int a, int num)
		: _data(d, a, num)
	{}

	int d() const { return std::get<0>(_data); }
	int a() const { return std::get<1>(_data); }
	int num() const { return std::get<2>(_data); }

	std::tuple<int, int, int> _data;
};

struct greatera
{
	bool operator()(const P &lhs, const P &rhs)
	{
		return lhs.a() > rhs.a();
	}
};

struct lesserd
{
	bool operator()(const P &lhs, const P &rhs)
	{
		return lhs.d() < rhs.d();
	}
};

template <class T>
bool checkContainer(T &cont, long long &Z, std::vector<int> &resvec)
{
	bool result = true;

	for (auto &it : cont)
	{
		if (Z > it.d())
		{
			Z = Z - it.d() + it.a();
			resvec.push_back(it.num());
		}
		else
		{
			result = false;
		}
	}

	return result;
}
int main()
{
	int N;
	long long Z;
	scanf("%d %lld ", &N, &Z);

	std::multiset<P, lesserd> inc;
	std::multiset<P, greatera> dec;

	std::vector<int> result;
	result.reserve(N);

	for (int i = 0; i < N; i++)
	{
		int d, a;
		scanf("%d %d ", &d, &a);
		if (d>a)
		{
			// decreases life
			dec.insert(P(d, a, i+1));
		}
		else
		{
			inc.insert(P(d, a, i+1));
		}
	}

	bool yes = checkContainer(inc, Z, result);
	if (yes)
	{
		yes = checkContainer(dec, Z, result);
	}
	printf("%s\n", yes ? "TAK" : "NIE");
	if (yes)
	{
		std::for_each(result.begin(), result.end(), [](int &x) { printf("%d ", x); });
		printf("\n");
	}

	return 0;
}