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

int *a, *d, *s;

int porow(const void *e1, const void *e2)
{
    int i1 = *(int *) e1;
    int i2 = *(int *) e2;
    int a1, a2, d1, d2, r1, r2, wyn;

    d1 = d[i1];
    d2 = d[i2];
    a1 = a[i1];
    a2 = a[i2];
    r1 = d1 - a1;
    r2 = d2 - a2;
    if (r1 <= 0)
    {
        if (r2 <= 0)
        {
            wyn = d1 - d2;
            if (wyn == 0)
                wyn = a2 - a1;
        }
        else
            wyn = -1;
    }
    else if (r2 > 0)
    {
        wyn = d2 - d1;
        if (wyn == 0)
            wyn = a2 - a1;
    }
    else
        wyn = 1;
    return wyn;
}

int main()
{
    int i, n, z, ok;
    long long z2;

    scanf("%d%d", &n, &z);
    a = malloc(n * sizeof(int));
    d = malloc(n * sizeof(int));
    s = malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
    {
        scanf("%d%d", d + i, a + i);
        s[i] = i;
    }
    qsort(s, n, sizeof(int), porow);
    for (ok = 1, z2 = z, i = 0; ok && i < n; i++)
    {
        z2 -= d[s[i]];
        if (z2 <= 0)
            ok = 0;
        else
            z2 += a[s[i]];
    }
    if (ok)
    {
        printf("TAK\n");
        for (i = 0; i < n; i++)
            printf("%s%d", i > 0 ? " " : "", s[i] + 1);
        printf("\n");
    }
    else
        printf("NIE\n");
    free(s);
    free(d);
    free(a);
    return 0;
}