Hero

Bitor must defeat n monsters in some order with starting health z. Monster i deals d_i damage and then restores a_i health if defeated. Health must stay positive throughout. Decide if all monsters can be defeated and output one winning order.

The first line has n and z. The next n lines give d_i and a_i.

Print NIE if impossible. Otherwise print TAK on the first line and a permutation on the second line.

• $1 \leq n, z \leq 100{,}000$