Description

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.

Input Format

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$.

Output Format

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.)

3 5
3 1
4 8
8 3

TAK
2 3 1 

Hint

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