[PA2014] Bohater
题目描述
在一款电脑游戏中,你需要打败 $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**)
输入输出样例
输入样例 #1
3 5
3 1
4 8
8 3
输出样例 #1
TAK
2 3 1
说明
对于 $100\%$ 的数据,$1\le n,z\le 10^5$,$0\le d_i,a_i\le 10^5$。