P4025 [PA 2014] Bohater

In a computer game, you need to defeat $n$ monsters (numbered from $1$ to $n$). To defeat monster $i$, you need to spend $d_i$ health points, but after the monster dies, it drops a healing potion that restores $a_i$ health points. At any time, your health must not drop to $0$ (or below). Determine whether there exists an order of fighting such that you can defeat all $n$ monsters without dying.

The first line contains two integers $n, z$, representing the number of monsters and your initial health. The next $n$ lines each contain two integers $d_i, a_i$.

The first line is `TAK` (yes) or `NIE` (no), indicating whether such an order exists. If the first line is `TAK`, then the second line contains a permutation of $1\sim n$ separated by spaces, representing a valid order. If there are multiple answers, you may output any one of them. (**This problem uses SPJ.**)

For $100\%$ of the testdata, $1 \le n, z \le 10^5$, $0 \le d_i, a_i \le 10^5$. Translated by ChatGPT 5