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

typedef long long LL;

struct Beast
{
    int n, damage, heal;
};

struct WeakBeast
{
    bool operator() (const Beast& beast) const
    {
        return beast.heal - beast.damage >= 0;
    }
};

struct DamageOrder
{
    bool operator() (const Beast& lhs, const Beast& rhs) const
    {
        return lhs.damage < rhs.damage;
    }
};

struct HealOrder
{
    bool operator() (const Beast& lhs, const Beast& rhs) const
    {
        return lhs.heal > rhs.heal;
    }
};

int main()
{
    std::ios_base::sync_with_stdio(0);
    size_t n;
    LL hp;
    std::cin >> n >> hp;

    std::vector<Beast> beasts;
    for (size_t i=1; i<=n; ++i)
    {
        Beast beast;
        beast.n = i;
        std::cin >> beast.damage >> beast.heal;
        beasts.push_back(beast);
    }

    std::vector<Beast>::iterator bound =
            std::partition(beasts.begin(), beasts.end(), WeakBeast());
    std::sort(beasts.begin(), bound, DamageOrder());
    std::sort(bound, beasts.end(), HealOrder());

    bool alive = true;
    for (std::vector<Beast>::const_iterator it=beasts.begin(); it!=beasts.end(); ++it)
    {
        hp -= it->damage;
        if (hp <= 0) {
            alive = false;
            break;
        }
        hp += it->heal;
    }

    if (!alive) {
        std::cout << "NIE" << std::endl;
    }
    else {
        std::cout << "TAK" << std::endl;
        for (std::vector<Beast>::const_iterator it=beasts.begin(); it!=beasts.end(); ++it)
        {
            std::cout << it->n << ' ';
        }
        std::cout << std::endl;
    }

    return 0;
}