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
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;

struct monster{
    int dmg;
    int pot;
    int nr;
};

bool compare(const monster& x,const monster& y){
     return x.dmg < y.dmg;
}

bool czy=1;
int n, ilep, ilen, a, b;
long long int hp, absol;
monster mob;
vector <monster> pos, neg;

int main()
{
    scanf("%d %I64d", &n, &hp );
    for(int z=1; z<=n; z++)
    {
        scanf("%d %d", &mob.dmg, &mob.pot);
        mob.nr=z;
        absol+=mob.pot-mob.dmg;
        if(mob.pot-mob.dmg >= 0){
            pos.push_back(mob);
            ilep++;
        }
        else{
            neg.push_back(mob);
            ilen++;
        }
    }
    if(hp+absol<=0)
        printf("NIE\n");
    else{
        sort(pos.begin(), pos.end(), compare);
        for(int x=0; x<ilep; x++)
        {
            hp-=pos[x].dmg;
            if(hp<=0){
                czy=0;
                x=ilep+1;
            }
            else
                hp+=pos[x].pot;
        }
        if(czy==1){
            sort(neg.begin(), neg.end(), compare);
            for(int c=ilen-1; c>=0; c--)
            {
                hp-=neg[c].dmg;
                if(hp<=0){
                    czy=0;
                    c=-1;
                }
                else
                    hp+=neg[c].pot;
            }
        }
        if(czy==0)
            printf("NIE\n");
        else
        {
            printf("TAK\n");
            for(int v=0;v<ilep;v++)
                printf("%d ", pos[v].nr);
            for(int m=ilen-1; m>=0; m--)
                printf("%d ", neg[m].nr);
            printf("\n");
        }
    }

    return 0;
}