洛谷 P4025 · 难度 提高+/省选−

题目描述

在一款电脑游戏中，你需要打败 $n$ 只怪物（从 $1$ 到 $n$ 编号）。

为了打败第 $i$ 只怪物，你需要消耗 $d_i$ 点生命值，但怪物死后会掉落血药，使你恢复 $a_i$ 点生命值。

任何时候你的生命值都不能降到 $0$（或 $0$ 以下）。

请问是否存在一种打怪顺序，使得你可以打完这 $n$ 只怪物而不死掉。

输入格式

第一行两个整数 $n,z$，分别表示怪物的数量和你的初始生命值。

接下来 $n$ 行，每行两个整数 $d_i,a_i$。

输出格式

第一行为 TAK（是）或 NIE（否），表示是否存在这样的顺序。

如果第一行为 TAK，则第二行为空格隔开的 $1\sim n$ 的排列，表示合法的顺序。

如果答案有很多，你可以输出其中任意一个。（本题使用 SPJ）

说明/提示

对于 $100\mathrm{\%}$ 的数据，$1\le n,z\le {10}^5$，$0\le d_i,a_i\le {10}^5$。

样例

样例 1

输入

3 5
3 1
4 8
8 3

输出

TAK
2 3 1