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
//
//  main.cpp
//  Bohater2
//
//  Created by Wiktor  on 14/05/14.
//  Copyright (c) 2014 Wiktor . All rights reserved.
//

#include <iostream>
#include <algorithm>

using namespace std;

const int MAX_P = 100000;

struct Potwor {
    int d;
    int a;
    int i;
};

int nd=0, no=0;
Potwor dodaja[MAX_P];
Potwor odejmuja[MAX_P];

bool latwy (Potwor i, Potwor j) {
    return i.d<j.d;
}

bool dodaje (Potwor i, Potwor j) {
    if(i.a>j.a) {
        return true;
    } else if(i.a==j.a){
        return i.d<j.d;
    } else {
        return false;
    }
}

int main(int argc, const char * argv[])
{
    ios_base::sync_with_stdio(false);

    int n, hp;
    int a,d;
    cin >> n; cin >> hp;

    for(int i=0; i<n; ++i) {
        cin >> d; cin >>a;
        if(a>=d) {
            dodaja[nd].d=d;
            dodaja[nd].a=a;
            dodaja[nd].i=i+1;
            ++nd;
        } else {
            odejmuja[no].d=d;
            odejmuja[no].a=a;
            odejmuja[no].i=i+1;
            ++no;
        }
    }

    sort(dodaja, dodaja+nd, latwy);
    sort(odejmuja, odejmuja+no, dodaje);

    for(int j=0; j<nd; ++j) {
        hp-=dodaja[j].d;
        if(hp<=0) {
            cout << "NIE\n";
            return 0;
        }
        hp+=dodaja[j].a;
    }

    for(int j=0; j<no; ++j) {
        hp-=odejmuja[j].d;
        if(hp<=0) {
            cout << "NIE\n";
            return 0;
        }
        hp+=odejmuja[j].a;
    }

    cout << "TAK\n";
    for(int j=0; j<nd; ++j) {
        cout << dodaja[j].i << " ";
    }

    for(int j=0; j<no; ++j) {
        cout << odejmuja[j].i << " ";
    }

    return 0;
}