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

const int MAX = 100003;

using namespace std;

struct potwor_dodatni
{
    int d, a, n;    // n - nr potwora
};

bool operator<(potwor_dodatni pot1, potwor_dodatni pot2)
{
    return (pot1.d<pot2.d)? true: false;
}

struct potwor_ujemny
{
    int d, a, n;
};

bool operator<(potwor_ujemny pot1, potwor_ujemny pot2)
{
    return (pot1.a<pot2.a)? false: true;
}

int main()
{
    int n, d, a, s;
    int nr_tab1=0, nr_tab2=0;
    long long z;
    potwor_dodatni tab1[MAX];
    potwor_ujemny tab2[MAX];

    scanf("%d%lld", &n, &z);
    for(int i=0; i<n; ++i)
    {
        scanf("%d%d", &d, &a);
        s=d-a;
        if(s<=0)
        {
            tab1[nr_tab1].n=i+1;
            tab1[nr_tab1].a=a;
            tab1[nr_tab1].d=d;
            nr_tab1++;
        }
        else
        {
            tab2[nr_tab2].n=i+1;
            tab2[nr_tab2].a=a;
            tab2[nr_tab2].d=d;
            nr_tab2++;
        }
    }

    sort(tab1, tab1+nr_tab1);
    sort(tab2, tab2+nr_tab2);

/*  Testy: in1.in i in2.in
    for(int i=0; i<nr_tab1; i++)
        printf("%d\n", tab1[i].n);
    printf("\n");
    for(int i=0; i<nr_tab2; i++)
        printf("%d\n", tab2[i].n);
*/


    int res[MAX];   // kolejka z odpowiedziami
    for(int i=0; i<nr_tab1; ++i)
    {
        z-=tab1[i].d;
        if(z<=0)
        {
            printf("NIE");
            return 0;
        }
        z+=tab1[i].a;
        res[i]=tab1[i].n;
    }

    for(int i=0; i<nr_tab2; ++i)
    {
        z-=tab2[i].d;
        if(z<=0)
        {
            printf("NIE");
            return 0;
        }
        z+=tab2[i].a;
        res[nr_tab1+i]=tab2[i].n;
    }
    printf("TAK\n");
    for(int i=0; i<nr_tab1+nr_tab2; ++i)
        printf("%d ", res[i]);

    return 0;
}