Hero

Time limit1sMemory limit256 MB

Summary

Order n monsters so a hero with health z survives each d_i hit and collects each a_i reward, printing TAK with the order or NIE.

Level: Medium6 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

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.

Input

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

Output

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

Constraints

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

Examples1

Example 1
Input
```
3 5
3 1
4 8
8 3
```
Expected output
```
TAK
2 3 1
```