CF913D.Too Easy Problems

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__p__j.

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.

你正在为一场关于调度理论的考试做准备。考试时长恰好为 $T$ 毫秒，共包含 $n$ 道题目。对于第 $i$ 道题，你可以选择花费恰好 $t_i$ 毫秒将其解出，也可以选择忽略它，从而不花费任何时间。解完一道题后，你无需额外休息时间。

遗憾的是，老师认为其中一些题目对你而言过于简单。因此，他为每道题 $i$ 分配了一个整数 $a_i$，其含义是：仅当你在整场考试中解出的题目总数（含本题）不超过 $a_i$ 时，该题才能为你最终得分贡献 1 分。

形式化地，假设你在考试中解出了题目 $p_1,\,p_2,\,\dots,\,p_k$（共 $k$ 道）。那么你的最终得分 $s$ 等于满足 $k \le a_{p_j}$ 的下标 $j$（其中 $1 \le j \le k$）的个数。

你已猜到考试的第一道真实题目就摆在眼前。因此，你希望预先选定一组题目来求解，使得最终得分最大化。请注意：考试有严格的时间限制，你必须确保所选题目的总耗时不超过 $T$。若存在多个不同题目集合均可达到最大最终得分，输出任意一个即可。

The first line contains two integers n and T (1 ≤ n ≤ 2·105; 1 ≤ T ≤ 109) — 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 ≤ 104). The problems are numbered from 1 to n.

第一行包含两个整数 $n$ 和 $T$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq T \leq 10^9$），分别表示考试中的题目数量和考试时长（单位：毫秒）。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $t_i$（$1 \leq a_i \leq n$；$1 \leq t_i \leq 10^4$）。题目编号从 $1$ 到 $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.

第一行输出一个整数 $s$ —— 你可能获得的最高最终得分。

第二行输出一个整数 $k$（$0 \leq k \leq n$）—— 你需要解决的问题个数。

第三行输出 $k$ 个互不相同的整数 $p_1,\ p_2,\ \dots,\ p_k$（$1 \leq p_i \leq n$）—— 你需要解决的问题的编号，顺序任意。

若存在多个最优的问题集合，输出其中任意一个即可。

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.

在第一个例子中，你应该解决第 3、第 1 和第 4 题。此时你将花费 $80 + 100 + 90 = 270$ 毫秒，这在考试时长（300 毫秒）范围内（甚至还能剩下 30 毫秒休息）。第 3 题和第 1 题各为你带来 1 分，而第 4 题则不能得分。你的总得分为 2 分。

在第二个例子中，考试时长严重不足，甚至连一道题都无法完成。

在第三个例子中，你恰好有足够的时间在 $42 + 58 = 100$ 毫秒内解决两道题，并微笑着将解答交给老师。