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
#include <stdlib.h>
#include <cstdio>
#include <algorithm>
#include<iterator>
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <deque>
#define FOR(x,z) for(int x=0;x<(z);++x)
#define DS(i) fprintf(stderr, "DEBUG: %s\n",i);
#define DI(i) fprintf(stderr, "DEBUG: %d\n",i);
#define DF(i) fprintf(stderr, "DEBUG: %f\n",i);
using namespace std;

long long hp;
int N;
bool por(pair<pair<int, int>,int>x, pair<pair<int,int>,int> y)
{
    return (x.first.second - x.first.first) < (y.first.second - y.first.first);
}
void wykonaj()
{
    deque<pair<pair<int, int>, int> > pot1, pot2;
    scanf("%d %lld", &N, &hp);
    long long thp=hp;
    int a,b;
    FOR(i,N)
    {
        scanf("%d %d", &a, &b);
        if(a>b)
            pot1.push_back(make_pair(make_pair(a,b),i+1));
        else
            pot2.push_back(make_pair(make_pair(a,b),i+1));

        thp+=b-a;
    }
    if(thp<=0)
    {
        printf("NIE\n");
        return;
    }
    sort(pot2.begin(), pot2.end());
    sort(pot1.begin(), pot1.end(),greater<pair<pair<int, int>, int> >());
    stable_sort(pot1.begin(), pot1.end(),por);
//    FOR(i,pot1.size())
//    {
//        printf("%d %d\n", pot1[i].first.first, pot1[i].first.second);
//    }
//    FOR(i,pot2.size())
//    {
//        printf("%d %d\n", pot2[i].first.first, pot2[i].first.second);
//    }
    deque<int> kol;
    while(pot2.size()>0)
    {
        //printf("%lld %d %d\n",hp, pot2.front().first.first,pot2.front().first.second);
        if(pot2.front().first.first<hp)
        {
            kol.push_back(pot2.front().second);
            hp-=pot2.front().first.first;
            hp+=pot2.front().first.second;
            pot2.pop_front();
        }
        else
        {
            printf("NIE\n");
            return;
        }
    }
    //printf("tu?\n");
    while(pot1.size()>0)
    {
        //printf("%lld %d %d\n",hp, pot1.front().first.first,pot1.front().first.second);
        if(pot1.front().first.first<hp)
        {

            kol.push_back(pot1.front().second);
            hp-=pot1.front().first.first;
            hp+=pot1.front().first.second;
            pot1.pop_front();
        }
        else
        {
            printf("NIE\n");
            return;
        }
    }
    printf("TAK\n");
    copy(kol.begin(),kol.end(),ostream_iterator<int>(cout, " "));
    printf("\n");
}

int main()
{
//    int T;
//    scanf("%d",&T);
//    for(int t=1;t<=T;t++)
//    {
        //wczytaj();
     //   DI(t)
        //printf("Case #%d: ",t);
        wykonaj();
    //}
    return 0;
}