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 <cstdlib>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <functional>
#include <set>
#include <vector>

using namespace std;

int main()
{
	typedef std::pair<int, int> para; // koszt, id potwora

	typedef std::pair<int, para> trojka;

	std::set<trojka> bilans_dodatni;
	std::set<trojka> bilans_ujemny;

	set<trojka> :: iterator it;
	set<trojka>::reverse_iterator rit;

	vector<int> result;

	int n;
	long long z;
	int d,a;
	int bilans;

	cin >> n;
	cin >> z;

	for (int i=0;i<n ;i++)
	{
        scanf("%d%d", &d, &a);
		bilans = a-d;


		if (bilans>=0)
		{
            para p;
            p.first = a;   // to co dodaje
            p.second = i;  // indeks

            trojka t;
            t.first = d;  //koszt
            t.second = p;

			bilans_dodatni.insert(t);
		}
		else
		{
            para p;
            p.first = d;   // koszt
            p.second = i;  // indeks

            trojka t;
            t.first = a;  //to co dodaje
            t.second = p;

            bilans_ujemny.insert(t);
		}
	}

	bool fail = false;

	for (it = bilans_dodatni.begin(); it!=bilans_dodatni.end() && fail==false; it++)
	{
        trojka m = *it;

		if (m.first>=z)
		{
			fail = true;
		}
		else
		{
			z = z - m.first;
			z = z + m.second.first;
			result.push_back(m.second.second +1 );
		}
    }

	for (rit = bilans_ujemny.rbegin(); rit!=bilans_ujemny.rend() && fail==false; ++rit)
	{
        trojka m = *rit; // returns pair to m

		if (m.second.first>=z)
		{
			fail = true;
		}
		else
		{
			z = z - m.second.first;
            z = z + m.first;
			result.push_back(m.second.second +1);
		}
    }

	if (fail==true)
	{
		cout << "NIE" << endl;
	}
	else
	{
		cout << "TAK" << endl;
		for( std::vector<int>::const_iterator i = result.begin(); i != result.end(); ++i)
			 std::cout << *i << ' ';
	}
	return 0;
}