题目描述

题目译自 PA 2014 Runda 2 Bohater

拜托克超市的货架上刚刚上架了一款新的电脑游戏，玩家在游戏中操控勇敢的英雄 Bitor，任务是击败居住在拜托格勒地牢中的 $n$ 只怪物。为简化起见，我们将怪物编号为从 $1$ 到 $n$。

在与编号为 $i$ 的怪物战斗时，Bitor 会受到伤害，损失 $d_{i}$ 点生命值。该怪物守卫着一个装有健康药水的宝箱，战胜怪物后，Bitor 可以喝下药水，恢复 $a_{i}$ 点生命值。

Bitor 能轻松击败怪物，但他不能让自己的生命值在任何时候降至 $0$ 或以下。Bitor 是否可以通过某种顺序与怪物战斗，成功击败所有怪物？

输入格式

输入数据的第一行包含两个整数 $n$ 和 $z$ $(1 \leq n, z \leq 100000)$，分别表示怪物数量和 Bitor 的初始生命值。

接下来的 $n$ 行描述怪物：第 $i$ 行包含两个整数 $d_{i}$ 和 $a_{i}$ $(0 \leq d_{i}, a_{i} \leq 100000)$，分别表示编号为 $i$ 的怪物造成的伤害和击败它后获得的药水恢复的生命值。

输出格式

输出的第一行应包含一个字符串 TAK 或 NIE，表示 Bitor 是否能够击败所有怪物。

如果可以击败所有怪物，则应输出第二行，包含 $n$ 个互不相同的整数，范围从 $1$ 到 $n$，用单个空格分隔。此序列应描述一个可行的战斗顺序，序列中的每个数字对应依次击败的怪物编号。

如果存在多个正确答案，你的程序可以输出其中任意一个。

3 5
3 1
4 8
8 3

TAK
2 3 1