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
#include <iostream>
#include "stdio.h"
#include <list>

using namespace std;

const short INDEKS = 0;
const short MOC_POTWORA = 1;
const short ELIKSIR = 2;

struct Element {
   int ele[3];
};

bool porownanie_bilans(const Element& a, const Element& b) {
    return (a.ele[ELIKSIR] - a.ele[MOC_POTWORA]) < (b.ele[ELIKSIR] - b.ele[MOC_POTWORA]);
};

bool porownanie_eliksir(const Element& a, const Element& b) {
    return a.ele[ELIKSIR] > b.ele[ELIKSIR];
};

bool porownanie_moc_potwora(const Element& a, const Element& b) {
    return a.ele[MOC_POTWORA] < b.ele[MOC_POTWORA];
};

void wypisz_liste(list<Element> lista)
{
    list<Element>::iterator iter;
    for( iter=lista.begin();  iter != lista.end(); ++ iter) {
        cout << (* iter).ele[INDEKS] << " " << (* iter).ele[MOC_POTWORA] << " " << (* iter).ele[ELIKSIR] << endl;
    }
    cout << endl;

}


int main()
{
    ios_base::sync_with_stdio(0);
    int potwory, zycie, moc_potwora;
    long zycie_akt;
    list<int> zabite_potwory;

    scanf("%d%d", &potwory, &zycie_akt);
//    cout << "potwory : " << potwory << " zycie_akt : " << zycie_akt << endl;
    list<Element> lista_bilans_plus;
    list<Element> lista_bilans_minus;

    for (int i=0;i<potwory;i++) {
        scanf("%d%d", &moc_potwora, &zycie);
        Element elem;
        elem.ele[INDEKS] = i+1;
        elem.ele[MOC_POTWORA] = moc_potwora;
        elem.ele[ELIKSIR] = zycie;
        (elem.ele[ELIKSIR] - elem.ele[MOC_POTWORA]) < 0 ? lista_bilans_minus.push_back(elem) : lista_bilans_plus.push_back(elem);
    }

    lista_bilans_plus.sort(porownanie_moc_potwora);
    lista_bilans_minus.sort(porownanie_eliksir);
//    cout << "lista plus : " << endl; ;
//    wypisz_liste(lista_bilans_plus);
//    cout << "lista minus : " << endl;
//    wypisz_liste(lista_bilans_minus);

    list<Element>::iterator iter;
    for( iter=lista_bilans_plus.begin();  iter != lista_bilans_plus.end(); ++ iter) {
        if (zycie_akt - (* iter).ele[MOC_POTWORA] < 0) {
            cout << "NIE" << endl;
            return 0;
        } else
        {
            zycie_akt = zycie_akt + ((* iter).ele[ELIKSIR] - (* iter).ele[MOC_POTWORA]);
            zabite_potwory.push_back((* iter).ele[INDEKS]);
        }
    }

    for( iter=lista_bilans_minus.begin();  iter != lista_bilans_minus.end(); ++ iter) {
        if (zycie_akt - (* iter).ele[MOC_POTWORA] < 0) {
            cout << "NIE" << endl;
            return 0;
        } else
        {
            zycie_akt = zycie_akt + ((* iter).ele[ELIKSIR] - (* iter).ele[MOC_POTWORA]);
            zabite_potwory.push_back((* iter).ele[INDEKS]);
        }
    }

    cout << "TAK" << endl;

    list<int>::iterator iter_int;
    for( iter_int=zabite_potwory.begin();iter_int != zabite_potwory.end(); ++ iter_int) {
        cout << (* iter_int) << " ";
    }

    return 0;

}