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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <queue>

using namespace std;

//pomysl: najpierw odwiedzamy wszystkie potwory z dodatnim saldem, bo po nich mamy wiecej zycia
// potem z ujemnym, ale idziemy od konca. Walczymy ze wszystkimi, wiec wiemy, ile dokladnie na koniec
// bedziemy miec zycia. Teraz 'cofamy sie' i wybieramy potwora z eliksirem mniejszym od ilosci zycia, ktora nam pozostala
// (bo przed wypiciem musial miec zycie >=0) oraz takiego, ktory jednoczesnie ma najmniejsze saldo (najwiecej traci)
//(bo chcemy jak najdluzej miec jak najwiecej zycia)

int main() {
    
    int n;
    int a;
    
    scanf("%d%d",&n,&a);
    
    long long int life = a;
    long long int endLife = life; //ile zycia bedziemy miec na koniec
    
    int monster[n]; //ile zycia zabierze nam potwor
    int eliksir[n]; //ile zycia odzyskamy po walce
    vector< pair<int,int> > good; //lista par ile zabierze potwor + nr potwora dla tych potorow, dla ktorych po walce mamy wiecej zycia
    vector< pair<int,int> > bad; //lista par ile da eliksir + nr potwora dla tych potworow, dla ktorych po walce mamy mniej zycia (lub rowno)
    
    priority_queue< pair<int,int> > q; //kolejka z priorytetem bedacym saldem, druga wartosci to nr potwora
    
    
    for (int i=0; i<n; i++)
    {
        scanf("%d%d", &monster[i], &eliksir[i]);
        endLife = endLife - monster[i] + eliksir[i];
        
        if (eliksir[i] - monster[i] > 0) //dodatnie saldo walki
        {
            pair<int,int> p;
            p.first = monster[i];
            p.second = i;
            good.push_back(p);
        }
        else //ujemne saldo walki
        {
            pair<int,int> p;
            p.first = eliksir[i];
            p.second = i;
            bad.push_back(p);
        }
        
    }
    
    if (endLife <= 0)
    {
    	printf("NIE\n");
    	return 0;
    }
    
    sort(good.begin(), good.end());
    sort(bad.begin(), bad.end());
    
    vector<int> result;
    vector<int> resultReverse; //czesc rozwiazania zawierajaca potwory z ujemnym saldem (odwrocona)
    
    bool isOK = true;
    
    //wypelnianie wynikow potworami z dodatnim saldem
    for (int i=0; i<good.size(); i++)
    {
        if (life > good[i].first)
        {
            life = life - monster[good[i].second] + eliksir[good[i].second];
            result.push_back(good[i].second);
        }
        else
        {
            isOK = false;
            break;
        }
    }
    
    if (!isOK)
    {
        printf("NIE\n");
        return 0;
    }
    
    //wypelnianie wyniku potworami z ujemnym saldem
    int i=0;
    while (resultReverse.size() != bad.size())
    {
    	while (i < bad.size() && endLife > bad[i].first)
    	{
    		pair<int, int> p;
    		p.first = monster[bad[i].second]-eliksir[bad[i].second];
    		p.second = bad[i].second;
    		q.push(p);
    		i++;
    	}
    	
    	if (q.empty())
    	{
    		isOK = false;
    		break;
    	}
    	
    	pair<int,int> best = q.top();
    	q.pop();
    	endLife = endLife + best.first;
    	resultReverse.push_back(best.second);
    }

    
    if (!isOK)
        printf("NIE\n");
    else
    {
        printf("TAK\n");
        for (int i=0; i<result.size(); i++)
            printf("%d ",result[i]+1);
        for (int i=resultReverse.size()-1; i>=0; i--)
            printf("%d ",resultReverse[i]+1);
        printf("\n");
    }
        
}