[PA2014]Bohater

Description

在一款电脑游戏中，你需要打败$n$只怪物（从$1$到$n$编号）。为了打败第$i$只怪物，你需要消耗$d_i$点生命值，但怪物死后会掉落血药，使你恢复$a_i$点生命值。任何时候你的生命值都不能降到$0$（或$0$以下）。请问是否存在一种打怪顺序，使得你可以打完这$n$只怪物而不死掉。

Input

第一行两个整数$n,z$($1 \le n,z \le 100000$)，分别表示怪物的数量和你的初始生命值。
接下来$n$行，每行两个整数$d_i,a_i$($0 \le d_i,a_i \le 100000$)。

Output

第一行为$TAK$（是）或$NIE$（否），表示是否存在这样的顺序。
如果第一行为$TAK$，则第二行为空格隔开的$1~n$的排列，表示合法的顺序。如果答案有很多，你可以输出其中任意一个。

Sample Input

3 5
3 1
4 8
8 3

Sample Output

TAK
2 3 1

HINT

Solution

把怪物分成两种，一种是$d_i \le a_i$，另一种$d_i \gt a_i$。
对于第一种，我们按$d_i$从小到大打，若某个怪兽打不掉了，那么不存在方案。这种贪心的正确性显而易见。
对于第二种，我们按$a_i$从大到小打，若某个怪兽打不掉了，那么不存在方案。那么我来证明一下这个的正确性。我们知道，打完所有的怪兽后的生命值是固定的，那么我们考虑从最后的生命值反着退回来，那么此时的就是先减去$a_i$，再加上$d_i$，如此下去。此时$a_i \lt d_i$，这么倒着做是不是与第一种情况一样？所以我们倒着按$a_i$从小到大做，就相当于正着按$a_i$从大到小做。

Standard

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
LL rest;
int a[N], b[N];
vector<int> ge, le;

bool Cmp1(int x, int y) {
    return a[x] < a[y];
}
bool Cmp2(int x, int y) {
    return b[x] > b[y];
}

int main() {
    scanf("%d%lld", &n, &rest);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i], &b[i]);
        if (a[i] <= b[i]) ge.push_back(i);
        else le.push_back(i);
    }
    sort(ge.begin(), ge.end(), Cmp1);
    sort(le.begin(), le.end(), Cmp2);
    for (int i = 0; i < (int)ge.size(); ++i) {
        if (rest <= a[ge[i]]) {
            puts("NIE");
            return 0;
        }
        rest += -a[ge[i]] + b[ge[i]];
    }
    for (int i = 0; i < (int)le.size(); ++i) {
        if (rest <= a[le[i]]) {
            puts("NIE");
            return 0;
        }
        rest += -a[le[i]] + b[le[i]];
    }
    puts("TAK");
    for (int i = 0; i < (int)ge.size(); ++i)
        printf("%d ", ge[i]);
    for (int i = 0; i < (int)le.size(); ++i)
        printf("%d ", le[i]);
    putchar('\n');
    return 0;
}