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
// Artur Minorczyk

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PI;
typedef vector<PI> VPI;
typedef long long LL;
#define FOR(x, b, e) for(int x = b; x <= (e); ++x)
#define FORD(x, b, e) for(int x = b; x >= (e); --x)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define VAR(v, n) __typeof(n) v = (n)
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(x) ((int)(x).size())
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
const int INF = 1000000001;
const double EPS = 10e-9;

struct Monster
{
	int first, second, id;
};
bool Compare(Monster a, Monster b)
{
	return a.ST == b.ST ? a.ND < b.ND : a.ST < b.ST;
}
bool CompareDiff(Monster a, Monster b)
{
	return a.ND == b.ND ? a.ST > b.ST : a.ND > b.ND;
}
int main()
{
    int n;
    LL z;
    Monster m;
    scanf("%d%lld", &n, &z);
    vector<Monster> mon[2];
    VI result(n), temp(n);
    REP(x, n)
    {
        scanf("%d%d", &m.ST, &m.ND);
        m.id = x + 1;
        if(m.ND - m.ST > 0) mon[0].PB(m);
        else mon[1].PB(m);
        
    }
    sort(ALL(mon[0]), Compare);
    sort(ALL(mon[1]), CompareDiff);
    REP(x, 2) FOREACH(it, mon[x])
    {
		z -= it->ST;
		if(z <= 0)
		{
			printf("NIE\n");
			return 0;
		}
		z += it->ND;
	}
    printf("TAK\n");
    REP(x, 2) FOREACH(it, mon[x]) printf("%d ", it->id);
    printf("\n");
    return 0;
}