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
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct pot
{
    int a,b,poz;
};
pot tab[100005];
pot tab2[100005];
vector <int> G,D;
int xtab=0;
int xtab2=0;
long long n,z;
long long suma;
bool cmp1(pot i,pot j)
{
    return i.a<j.a;
}
bool cmp2(pot i,pot j)
{
    return i.a-i.b<j.a-j.b;
}
bool cmp3(pot i,pot j)
{
    return i.a>j.a;
}
bool cmp4(pot i,pot j)
{
    return i.b>j.b;
}
void wypisz()
{
    cout<<"Tab1"<<endl;
    for(int i=0;i<xtab;i++)
    {
        cout<<tab[i].a<<" "<<tab[i].b<<endl;
    }
    cout<<endl;
    cout<<"Tab2"<<endl;
    for(int i=0;i<xtab2;i++)
    {
        cout<<tab2[i].a<<" "<<tab2[i].b<<endl;
    }
}
bool sprawdz()
{
    for(int i=0;i<xtab2;i++)
    {
        if(suma-tab2[i].a<=0)
        {
            return false;
        }
        suma+=tab2[i].b-tab2[i].a;
        D.push_back(tab2[i].poz);
        //cout<<suma<<endl;
    }
    return true;
}
void wypisz2()
{
    cout<<"TAK"<<endl;
    for(int i=0;i<G.size();i++) cout<<G[i]<<" ";
    for(int i=0;i<D.size();i++) cout<<D[i]<<" ";
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin>>n>>z;
    int a,b;
    for(int i=0;i<n;i++)
    {
        cin>>a>>b;
        if(a<=b)
        {
            tab[xtab].a=a;
            tab[xtab].b=b;
            tab[xtab++].poz=i+1;
        }
        else
        {
            tab2[xtab2].a=a;
            tab2[xtab2].b=b;
            tab2[xtab2++].poz=i+1;
        }
    }
    sort(tab,tab+xtab,cmp1);
    suma=z;
    for(int i=0;i<xtab;i++)
    {
        if(suma-tab[i].a<=0)
        {
            cout<<"NIE"<<endl;
            return 0;
        }
        suma+=tab[i].b-tab[i].a;
        G.push_back(tab[i].poz);
    }
    z=suma;
    sort(tab2,tab2+xtab2,cmp2);
    if(!sprawdz()) D.clear();
    else {wypisz2(); return 0;}
    suma=z;
    sort(tab2,tab2+xtab2,cmp3);
    if(!sprawdz()) D.clear();
    else {wypisz2(); return 0;}
    suma=z;
    sort(tab2,tab2+xtab2,cmp4);
    if(!sprawdz()) {D.clear();}
    else {wypisz2(); return 0;}
    cout<<"NIE"<<endl;
}