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
/*************************************************************************
 *   Zadanie:           Bohater                                          *
 *   Zlozonosc czasowa: O(n log n)                                       *
 *   Wynik:             --/10                                            *
 *************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define SIZE(c) (int) (c).size()
#define FOREACH(i,c) FOR(i,0,SIZE(c)-1)
#define PB push_back

using namespace std;

struct mon //ster
{
    int id;
    int d;
    int a;

    mon(int nid, int nd, int na)
        { id = nid; d = nd; a = na; }
};

bool comp(mon x, mon y)
{
    bool pos_x = (x.a >= x.d), pos_y = (y.a >= y.d);

    if (pos_x != pos_y)
        return (pos_x > pos_y);
    else if (pos_x)
        return (x.d < y.d);
    else
        return (x.a > y.a);
}

/*************************************************************************/

int main()
{
    ios_base::sync_with_stdio(0);

    int n;
    long long int z;

    cin >> n >> z;

    vector < mon > V;

    FOR(i,1,n)
    {
        int d, a;
        cin >> d >> a;

        V.PB( mon(i,d,a) );
    }

    sort(V.begin(), V.end(), comp);

    FOREACH(i,V)
    {
        if (z <= V[i].d)
        {
            cout << "NIE";
            return 0;
        }

        z -= V[i].d;
        z += V[i].a;
    }

    cout << "TAK" << '\n';
    FOREACH(i,V) cout << V[i].id << ' ';

    return 0;
}

/*************************************************************************/