Too Easy Problems

## 题目描述 你正在准备一场关于调度理论的考试。 这场考试会持续正好 $T$ 毫秒，由 $n$ 道题目组成。 你可以用 $t_i$ 毫秒解决第 $i$ 个问题，或者忽略它并不消耗时间。你也不需要用来在做完一道题之后休息的时间。 不幸的是，你的老师认为一些题目对你来说太简单了。因此，他对于每道题 $i$ 规定了一个整数 $a_i$，表示题目 $i$ 只在你总共解决了不超过 $a_i$ 个问题（包括问题 $i$ ）的情况下为你的最终成绩加上一分。 正式地，假设你在考试中解决了问题 $p_1,p_2,\cdots,p_k$。那么，你的最终成绩 $s$ 会等于在 $1$ 到 $k$ 之间的满足 $k\le a_{p_j}$ 的 $j$ 的个数。 你已经意识到这场考试真正的第一道题目已经放在了你面前。因此，你想要选择一组题目来解决，从而最大化你的最终成绩。不要忘记这场考试有时间限制，而你必须有足够的时间来解决所有你选择的题目。如果存在多个最优解，任意输出一组即可。 ## 输入格式 第一行包含 $2$ 个整数，$n$ 和 $T$，分别是考试中题目的数量和考试时长的毫秒数。 接下来的 $n$ 行每行包括两个整数 $a_i$ 和 $t_i$。题目编号从 $1$ 到 $n$。 ## 输出格式 在第一行，输出一个单独的整数 $s$，表示你的可能得到的最终成绩的最大值。 在第二行，输出一个单独的整数 $k$ 表示你应该解决的问题数量。 在第三行，以任意顺序输出 $k$ 个不同整数 $p_1,p_2,\cdots,p_k$，即你应当解决的题目编号。 如果有多个最优解，你可以输出其中任意一个。 ## 样例解释 在第一个样例中，你应该解决题目 $3$、$1$ 和 $4$。在这种解下你会花费 $80+100+90=270$ 毫秒，在考试的长度 $300$ms 以内（甚至给自己留出了 $30$ms 休息时间）。题目 $3$ 和题目 $1$ 会分别为你带来 $1$ 分，然而题目 $4$ 不会。你会得到 $2$ 分。 在第二个样例中，这场灾难性的考试的长度甚至不足以解决一道题目（所以你显然一分都得不到）。 在第三个样例中，你刚好有足够的时间 $(42+58=100)$ 来解决这两道题并且微笑着把答卷交给老师。 ## 数据范围 $1\le n\le 2\times10^5$ $1\le T\le10^9$ $0\le k\le n$

You are preparing for an exam on scheduling theory. The exam will last for exactly $ T $ milliseconds and will consist of $ n $ problems. You can either solve problem $ i $ in exactly $ t_{i} $ milliseconds or ignore it and spend no time. You don't need time to rest after solving a problem, either. Unfortunately, your teacher considers some of the problems too easy for you. Thus, he assigned an integer $ a_{i} $ to every problem $ i $ meaning that the problem $ i $ can bring you a point to the final score only in case you have solved no more than $ a_{i} $ problems overall (including problem $ i $ ). Formally, suppose you solve problems $ p_{1},p_{2},...,p_{k} $ during the exam. Then, your final score $ s $ will be equal to the number of values of $ j $ between 1 and $ k $ such that $ k<=a_{pj} $ . You have guessed that the real first problem of the exam is already in front of you. Therefore, you want to choose a set of problems to solve during the exam maximizing your final score in advance. Don't forget that the exam is limited in time, and you must have enough time to solve all chosen problems. If there exist different sets of problems leading to the maximum final score, any of them will do.

The first line contains two integers $ n $ and $ T $ ( $ 1<=n<=2·10^{5} $ ; $ 1<=T<=10^{9} $ ) — the number of problems in the exam and the length of the exam in milliseconds, respectively. Each of the next $ n $ lines contains two integers $ a_{i} $ and $ t_{i} $ ( $ 1<=a_{i}<=n $ ; $ 1<=t_{i}<=10^{4} $ ). The problems are numbered from 1 to $ n $ .

In the first line, output a single integer $ s $ — your maximum possible final score. In the second line, output a single integer $ k $ ( $ 0<=k<=n $ ) — the number of problems you should solve. In the third line, output $ k $ distinct integers $ p_{1},p_{2},...,p_{k} $ ( $ 1<=p_{i}<=n $ ) — the indexes of problems you should solve, in any order. If there are several optimal sets of problems, you may output any of them.

5 300
3 100
4 150
4 80
2 90
2 300

2
3
3 1 4

2 100
1 787
2 788

0
0

2 100
2 42
2 58

2
2
1 2

In the first example, you should solve problems 3, 1, and 4. In this case you'll spend $ 80+100+90=270 $ milliseconds, falling within the length of the exam, 300 milliseconds (and even leaving yourself 30 milliseconds to have a rest). Problems 3 and 1 will bring you a point each, while problem 4 won't. You'll score two points. In the second example, the length of the exam is catastrophically not enough to solve even a single problem. In the third example, you have just enough time to solve both problems in $ 42+58=100 $ milliseconds and hand your solutions to the teacher with a smile.