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

#define MAX 100000

struct ad {
    int a;
    int d;
    int i;
};

int compare (const void * a, const void * b)
{
    struct ad* a1 = (struct ad*)a;
    struct ad* b1 = (struct ad*)b;

    return ( b1->a - a1->a );
}

int main()
{
    int n, z, d, a, tmp;
    long long longZ, warKonieczny;
    int posTab[MAX][3]; // 0: index, 1: d, 2: a
    struct ad negTab[MAX];
    int posSize = 0, negSize = 0;
    char posKilled[MAX] = {0};
    int posMonsters;
    int killedOrder[MAX];
    int killedOrderSize = 0;
    char killedFlag;
    int i;

    scanf("%d %d", &n, &z);
    longZ = (long long)z;
    warKonieczny = longZ;
    for (i = 0; i < n; ++i) {
        scanf("%d %d", &d, &a);
        tmp = a - d;
        warKonieczny += (long long)tmp;
        if (tmp >= 0) {
            posTab[posSize][0] = i + 1;
            posTab[posSize][1] = d;
            posTab[posSize][2] = a;
            ++posSize;
        } else {
            negTab[negSize].i = i + 1;
            negTab[negSize].d = d;
            negTab[negSize].a = a;
            ++negSize;
        }
    }
    if (warKonieczny <= 0) {
        printf("NIE\n");
        return 0;
    }

    posMonsters = posSize;

    while (posMonsters > 0) {
        killedFlag = 0;
        for (i = 0; i < posSize; ++i) {
            if (posKilled[i] == 0 && longZ > (long long)posTab[i][1]) {
                longZ = longZ - (long long)posTab[i][1] + (long long)posTab[i][2];
                killedOrder[killedOrderSize] = posTab[i][0];
                posKilled[i] = 1;
                ++killedOrderSize;
                --posMonsters;
                killedFlag = 1;
            }
        }
        if (killedFlag == 0) {
            printf("NIE\n");
            return 0;
        }
    }

    qsort (negTab, negSize, sizeof(struct ad), compare);

    for (i = 0; i < negSize; ++i) {
        if (longZ > (long long)negTab[i].d) {
            longZ = longZ - (long long)negTab[i].d + (long long)negTab[i].a;
            killedOrder[killedOrderSize] = negTab[i].i;
            ++killedOrderSize;
        } else {
            printf("NIE\n");
            return 0;
        }
    }

    printf("TAK\n");
    for (i = 0; i < killedOrderSize; ++i) {
        printf("%d ", killedOrder[i]);
    }
    printf("\n");

    return 0;
}