Description：

$n$ 只怪物，打第 $i$ 只怪物需要消耗 $d[i]$ 点生命值，怪物死后恢复 $a[i]$ 点生命值。问是否存在一种打怪顺序，使得你可以打完这 $n$ 只怪物而不死掉。

$1\le n \le 100000$

Solution：

一个显然的贪心思路是先把所有怪按照消耗排序，先把能打的且回血的怪打了，如果这些怪都打不完的话那丢血的就更打不完了，把这些怪打完之后，剩下的就都是降血的了。因为剩下的都是降血的，所以现在打不了的留到以后就更打不了了，应该尽量使自己的血量保持，也就是说按回血量从高到低排序。

如果从另一个方向考虑，由于无论按什么顺序，只要打完了，最后剩余的血量是一定的，如果我么们倒着看整个过程，最后相当于失去恢复的血量，得到消耗的血量，按照之前的结论按消耗排序，也就是按回血排序。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,st;

#define MAXN 100010

struct monster

{

	long long d,a;

	int id;

}s[MAXN];

bool cmp_d_from_low_to_high(monster x,monster y){return x.d < y.d;}

bool cmp_a_from_high_to_low(monster x,monster y){return x.a > y.a;}

int ans[MAXN];

int main()

{

	scanf("%d%d",&n,&st);

	long long sum = st;

	for(int i = 1;i <= n;++i)scanf("%lld%lld",&s[i].d,&s[i].a);

	for(int i = 1;i <= n;++i)s[i].id = i;

	ans[0] = 0;

	sort(s + 1,s + 1 + n,cmp_d_from_low_to_high);

	for(int i = 1;i <= n;++i)

	{

		if(s[i].a > s[i].d)

		{

			if(sum <= s[i].d)

			{

				puts("NIE");

				return 0;

			}

			sum = sum - s[i].d + s[i].a;

			ans[++ans[0]] = s[i].id;

		}

	}

	sort(s + 1,s + 1 + n,cmp_a_from_high_to_low);

	for(int i = 1;i <= n;++i)

	{

		if(s[i].a <= s[i].d)

		{

			if(sum <= s[i].d)

			{

				puts("NIE");

				return 0;

			}

			sum = sum - s[i].d + s[i].a;

			ans[++ans[0]] = s[i].id;

		}

	}

	puts("TAK");

	for(int i = 1;i <= ans[0];++i)printf("%d ",ans[i]);

	puts("");

	return 0;

}