样例下载

题目描述

你正在打游戏。

要想通关，你需要消灭 $n$ 个敌人（编号为 1 ~ $n$）。

消灭敌人 $i$ 的过程会消耗你 $a_i$ 点的血量，但消灭它之后，你会得到 $b_i$ 点的血量回升。

初始时，你有 $s$ 点血量。在任意时刻，你的血量不能为零或为负。

问：如何安排消灭敌人的顺序，可以使得游戏顺利通关？

输入格式

第一行：包含两个整数 $n$, $s$

接下来 $n$ 行，每行包含两个整数 $a_i$, $b_i$。

输出格式

输出只有一行

如果不存在合理的方案，输出一个整数 -1

否则输出一行 $n$ 个数，表示你依次消灭的敌人的编号，数与数之间以一个空格隔开。如果存在多种方案，你只需要输出任意一种即可。

样例1输入

3 6
3 1
7 7
2 8

样例1输出

1 3 2

样例2输入

3 6
6 1
7 7
2 3

样例2输出

-1

提示

约 15% 的数据，$1 ≤ n ≤ 10$

100% 的数据，$1 ≤ n, s ≤ 10^5， 0 ≤ a_i, b_i ≤ 10^5$