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
#include <cstdlib>
#define __STDC_FORMAT_MACROS
#include <inttypes.h>
#include <climits>
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

struct Monster {
  int id, damage, potion;
  Monster() { }
  Monster(int const &id, int const &damage, int const &potion) : id(id), damage(damage), potion(potion) { }
  Monster(Monster const &o) : id(o.id), damage(o.damage), potion(o.potion) { }
  ~Monster() { }
};

bool compareMonstersByDamage(Monster const &a, Monster const &b) {
  return a.damage < b.damage;
}

bool compareMonstersByPotionsDesc(Monster const &a, Monster const &b) {
  return a.potion > b.potion;
}

int main(int const /*argc*/, char const * const * const /*argv*/) {
  int n, z;
  
  scanf("%d %d", &n, &z);
  
  vector<Monster> allMonsters(n);
  
  vector<int> result;
  
  for(int i = 0; i < n; ++i) {
    allMonsters[i].id = i + 1;
    scanf("%d %d", &(allMonsters[i].damage), &(allMonsters[i].potion));
  }
  
  sort(allMonsters.begin(), allMonsters.end(), compareMonstersByDamage);
  
  vector<Monster> badMonsters;
  
  for(int i = 0; i < n; ++i) {
    if(z <= allMonsters[i].damage) {
      printf("NIE\n");
      return EXIT_SUCCESS;
    }
    if(allMonsters[i].damage > allMonsters[i].potion) {
      badMonsters.push_back(allMonsters[i]);
    } else {
      result.push_back(allMonsters[i].id);
      z -= allMonsters[i].damage - allMonsters[i].potion;
    }
  }
  
  sort(badMonsters.begin(), badMonsters.end(), compareMonstersByPotionsDesc);
  
  for(unsigned int i = 0; i < badMonsters.size(); ++i) {
    if(z <= badMonsters[i].damage) {
      printf("NIE\n");
      return EXIT_SUCCESS;
    }
    result.push_back(badMonsters[i].id);
    z -= badMonsters[i].damage - badMonsters[i].potion;
  }
  
  printf("TAK\n");
  for(int i = 0; i < n; ++i) printf("%d ", result[i]);
  printf("\n");
  
  return EXIT_SUCCESS;
}