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

#define MAX 100001

using namespace std;

struct Beast {
  int nb;
  int takes;
  int gives;
};

Beast B[MAX];

bool CompareGood(const Beast& a, const Beast& b)
{
  return a.takes<b.takes;
};

bool CompareBad(const Beast& a, const Beast& b)
{
  return a.gives>b.gives;
};

int main()
{
  ios_base::sync_with_stdio(0);

  int n;
  long long z;
  cin >> n >> z;

  int nBad = MAX;
  int nGood = 0;
  int d,a;
  
  for(int i=1; i<=n; ++i)
  {
    cin >> d >> a;
    
    if(d<a)
    {
      B[nGood].takes = d;
      B[nGood].gives = a;
      B[nGood].nb = i;
      ++nGood;
    }
    else
    {
      --nBad;
      B[nBad].takes = d;
      B[nBad].gives = a;
      B[nBad].nb = i;
    }
  }

  sort(B,B+nGood,CompareGood);
  sort(B+nBad,B+MAX,CompareBad);
  
  for(int i=0; i<nGood; ++i)
  {
    z -= B[i].takes;
    if(z<=0)
    {
      cout << "NIE\n";
      return 0;
    }
    z += B[i].gives;
  }
  
  for(int i=nBad; i<MAX; ++i)
  {
    z -= B[i].takes;
    if(z<=0)
    {
      cout << "NIE\n";
      return 0;
    }
    z += B[i].gives;
  }
  
  cout << "TAK\n";
  for(int i=0; i<nGood; ++i)
  {
    cout << B[i].nb << " ";
  }
  
  for(int i=nBad; i<MAX; ++i)
  {
    cout << B[i].nb << " ";
  }
  cout <<"\n";
  
  return 0;
}