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

using namespace std;

typedef struct {
  int i,d,c;
} Monster;

Monster M[100005];

inline int pos(const int n) {
 return (n>=0) ? 1 : -1;
}

bool cmp(const Monster &a, const Monster &b) {
    int pa=pos(a.c);
    int pb=pos(b.c);

    return (pa==pb) ? (pa*(a.d-b.d) < 0) : (pa>pb);
}

int main()
{
    int n,z,d,a,i,j;
    long long P;

    scanf("%d%d",&n,&z);

    P=z;

    for (i=0; i<n; ++i) {
      scanf("%d%d",&d,&a);

      M[i].i = i+1;
      M[i].d = d;
      M[i].c = a-d;

      P+= a-d;
    }

    i=0;

    if (P>0) {
      sort(M,M+n,cmp);

      for (P=z; i<n && P>M[i].d; ++i) {
         P+=M[i].c;
      }
    }

    puts(i<n ? "NIE" :"TAK");

    for (j=0; j<i; ++j) printf("%d ",M[j].i);

    return 0;
}