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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <vector>
#include <sstream>
#define LL long long

using namespace std;

struct potwor
{
	int koszt_hp, zysk_hp, index, sumarum;
};

bool cmp(const potwor& i, const potwor& j) { return i.koszt_hp == j.koszt_hp ? j.sumarum < i.sumarum : i.koszt_hp < j.koszt_hp; }
//bool cmp2(const potwor& i, const potwor& j) { return i.koszt_hp == j.koszt_hp ? j.sumarum < i.sumarum : i.koszt_hp > j.koszt_hp; }
bool cmp2(const potwor& i, const potwor& j) { return i.sumarum == j.sumarum ? j.koszt_hp < i.koszt_hp : i.sumarum > j.sumarum; } //wzgledem sumarum
bool cmp3(const potwor& i, const potwor& j) { return i.sumarum == j.sumarum ? j.koszt_hp < i.koszt_hp : i.sumarum < j.sumarum; } //wzgledem sumarum v2
bool cmp4(const potwor& i, const potwor& j) { return i.koszt_hp == j.koszt_hp ? j.sumarum < i.sumarum : i.koszt_hp > j.koszt_hp; } //wzgledem hp v2
bool cmp5(const potwor& i, const potwor& j) { return i.zysk_hp == j.zysk_hp ? j.sumarum < i.sumarum : i.zysk_hp > j.zysk_hp; } //wzgledem dawanego v1
bool cmp6(const potwor& i, const potwor& j) { return i.zysk_hp == j.zysk_hp ? j.sumarum < i.sumarum : i.zysk_hp < j.zysk_hp; } //wzgledem dawanego v1

bool CheckifCan(vector<potwor>& v, LL& z, int &counter)
{
	for (auto i = v.begin(); i != v.begin() + counter; i++)
	{
		if (z - i->koszt_hp <= 0)
			return false;
		
		z += i->sumarum;
	}
	return true;
}

int main()
{
	//for (int g = 1; g <= 5000; g++)
	//{ 
		/*FILE * pFile;
		stringstream ss;
		ss << g << ".in";
		pFile = fopen(ss.str().c_str() , "r");

		FILE * pFileOut;
		stringstream ss1;
		ss1 <<  g << ".outt";
		pFileOut = fopen(ss1.str().c_str(), "w");*/

		int n;
		LL z;
		//fscanf(pFile, "%d %lld", &n, &z);
		scanf("%d %lld", &n, &z);
		vector<potwor> v1(n);
		vector<potwor> v2(n);
		int counter_v1 = 0, counter_v2 = 0;

		for (int i = 1; i <= n; i++)
		{
			potwor potw;
			//fscanf(pFile, "%d %d", &(potw.koszt_hp), &(potw.zysk_hp));
			scanf("%d %d", &(potw.koszt_hp), &(potw.zysk_hp));
			potw.index = i;
			potw.sumarum = potw.zysk_hp - potw.koszt_hp;

			if (potw.sumarum >= 0)
				v1[counter_v1++] = potw;
			else
				v2[counter_v2++] = potw;
		}

		sort(v1.begin(), v1.begin() + counter_v1, cmp);
		sort(v2.begin(), v2.begin() + counter_v2, cmp2);

		bool res = true;

		res = CheckifCan(v1, z, counter_v1);
		LL cpy = z;

		if (res)
		{
			z = cpy;
			res = CheckifCan(v2, z, counter_v2);

			if (!res)
			{
				res = true;
				sort(v2.begin(), v2.begin() + counter_v2, cmp3);
				z = cpy;
				res = CheckifCan(v2, z, counter_v2);

				if (!res)
				{
					res = true;
					sort(v2.begin(), v2.begin() + counter_v2, cmp4);
					z = cpy;
					res = CheckifCan(v2, z, counter_v2);

					if (!res)
					{
						res = true;
						sort(v2.begin(), v2.begin() + counter_v2, cmp5);
						z = cpy;
						res = CheckifCan(v2, z, counter_v2);

						if (!res)
						{
							res = true;
							sort(v2.begin(), v2.begin() + counter_v2, cmp6);
							z = cpy;
							res = CheckifCan(v2, z, counter_v2);
						}
					}

				}
			}
		}

		//fprintf(pFileOut, "%s\n", (res ? "TAK" : "NIE"));
		printf("%s\n", (res ? "TAK" : "NIE"));
		if (res)
		{
			for (auto i = v1.begin(); i != v1.begin() + counter_v1; i++)
				printf("%d ", i->index);
			for (auto i = v2.begin(); i != v2.begin() + counter_v2; i++)
				printf("%d ", i->index);
		}

		//fclose(pFileOut);
		//fclose(pFile);
	//}

	return 0;

}