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
#include <stdio.h>
#include <stdlib.h>

typedef struct {
        int id,diff,dmg,hp;
} Tmob;

static int cmpTmob(const void *a, const void *b) {
        Tmob *c,*d;
        c = (Tmob *)a;
        d = (Tmob *)b;
        if (c->diff > 0 && d->diff > 0) {
                return c->dmg - d->dmg;
        }

        if (c->diff < 0 && d->diff < 0) {
                return d->hp - c->hp;
        }

        return d->diff - c->diff;
}

int main(void) {
        int n,hp,i,a,b;
        Tmob *v;

        scanf("%d %d\n", &n, &hp);
        v = malloc(n*sizeof(*v));

        for (i=0; i<n; ++i) {
                scanf("%d %d\n", &a, &b);
                v[i].id = i+1;
                v[i].diff = b-a;
                v[i].dmg = a;
                v[i].hp = b;
        }

        qsort(v, n, sizeof(*v), cmpTmob);

        for (i=0; hp > 0 && i<n; ++i) {
                hp -= v[i].dmg;
                if (hp > 0) {
                        hp += v[i].dmg;
                        hp += v[i].diff;
                }
        }

        if (hp > 0) {
                printf("TAK\n%d", v[0].id);
                for (i=1; i<n; ++i)
                        printf(" %d", v[i].id);
                printf("\n");
        } else {
                printf("NIE\n");
        }

        return 0;
}