{"problem":{"name":"D. Too Easy Problems","description":{"content":"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF913D"},"statements":[{"statement_type":"Markdown","content":"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.\n\nUnfortunately, 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_).\n\nFormally, 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_.\n\nYou 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.\n\n## Input\n\nThe 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.\n\nEach 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\n## Output\n\nIn the first line, output a single integer _s_ — your maximum possible final score.\n\nIn the second line, output a single integer _k_ (0 ≤ _k_ ≤ _n_) — the number of problems you should solve.\n\nIn 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.\n\nIf there are several optimal sets of problems, you may output any of them.\n\n[samples]\n\n## Note\n\nIn 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.\n\nIn the second example, the length of the exam is catastrophically not enough to solve even a single problem.\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你正在为调度理论考试做准备。考试将持续恰好 $T$ 毫秒，包含 $n$ 道题目。你可以选择在恰好 $t_i$ 毫秒内解决第 $i$ 道题，或者忽略它且不花费任何时间。解决题目后也不需要休息时间。\n\n不幸的是，你的老师认为某些题目对你来说太简单了。因此，他为每道题 $i$ 分配了一个整数 $a_i$，表示只有当你除了题 $i$ 之外总共解决的题目数不超过 $a_i$ 时，题 $i$ 才能为你带来一分。\n\n形式化地，假设你在考试中解决了题目 $p_1, p_2, ..., p_k$。那么你的最终得分 $s$ 将等于满足 $k ≤ a_{p_j}$ 的 $j$（$1 ≤ j ≤ k$）的个数。\n\n你已经猜到考试的第一题就在你面前。因此，你希望提前选择一组题目来解决，以最大化你的最终得分。别忘了考试时间有限，你必须有足够的时间解决所有选中的题目。如果有多个集合能获得最大得分，任意一个都可以。\n\n第一行包含两个整数 $n$ 和 $T$（$1 ≤ n ≤ 2·10^5$；$1 ≤ T ≤ 10^9$）——考试中的题目数量和考试的时长（毫秒）。\n\n接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $t_i$（$1 ≤ a_i ≤ n$；$1 ≤ t_i ≤ 10^4$）。题目编号从 1 到 $n$。\n\n第一行输出一个整数 $s$ —— 你可能获得的最大最终得分。\n\n第二行输出一个整数 $k$（$0 ≤ k ≤ n$）—— 你应该解决的题目数量。\n\n第三行输出 $k$ 个互不相同的整数 $p_1, p_2, ..., p_k$（$1 ≤ p_i ≤ n$）—— 你要解决的题目的编号，顺序任意。\n\n如果存在多个最优解，你可以输出任意一个。\n\n在第一个例子中，你应该解决题目 3、1 和 4。这样你会花费 $80 + 100 + 90 = 270$ 毫秒，未超过考试时长 300 毫秒（甚至还能休息 30 毫秒）。题目 3 和 1 各给你一分，而题目 4 不会。你将获得两分。\n\n在第二个例子中，考试时间严重不足，甚至无法解决一道题。\n\n在第三个例子中，你刚好有足够的时间在 $42 + 58 = 100$ 毫秒内解决两道题，并面带微笑将答卷交给老师。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $T$（$1 ≤ n ≤ 2·10^5$；$1 ≤ T ≤ 10^9$）——考试中的题目数量和考试的时长（毫秒）。接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $t_i$（$1 ≤ a_i ≤ n$；$1 ≤ t_i ≤ 10^4$）。题目编号从 1 到 $n$。\n\n## Output\n\n第一行输出一个整数 $s$ —— 你可能获得的最大最终得分。第二行输出一个整数 $k$（$0 ≤ k ≤ n$）—— 你应该解决的题目数量。第三行输出 $k$ 个互不相同的整数 $p_1, p_2, ..., p_k$（$1 ≤ p_i ≤ n$）—— 你要解决的题目的编号，顺序任意。如果存在多个最优解，你可以输出任意一个。\n\n[samples]\n\n## Note\n\n在第一个例子中，你应该解决题目 3、1 和 4。这样你会花费 $80 + 100 + 90 = 270$ 毫秒，未超过考试时长 300 毫秒（甚至还能休息 30 毫秒）。题目 3 和 1 各给你一分，而题目 4 不会。你将获得两分。在第二个例子中，考试时间严重不足，甚至无法解决一道题。在第三个例子中，你刚好有足够的时间在 $42 + 58 = 100$ 毫秒内解决两道题，并面带微笑将答卷交给老师。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ n $ be the number of problems, $ T $ the total exam time (in milliseconds).\n- For each problem $ i \\in \\{1, 2, \\dots, n\\} $, let $ a_i \\in [1, n] $ be the maximum number of problems that can be solved for problem $ i $ to contribute a point, and $ t_i \\in [1, 10^4] $ be the time required to solve it.\n\n**Given:**\n\n- A set of $ n $ problems, each with pair $ (a_i, t_i) $.\n- Total available time: $ T $.\n- A subset $ S \\subseteq \\{1, 2, \\dots, n\\} $ of solved problems is feasible if $ \\sum_{i \\in S} t_i \\leq T $.\n\n**Objective:**\n\nMaximize the score $ s $, defined as:\n$$\ns = \\left| \\left\\{ i \\in S \\,\\middle|\\, |\\{ j \\in S \\mid j \\text{ is solved before or at the same time as } i \\}| \\leq a_i \\right\\} \\right|\n$$\n\n**Note:** Since the order of solving problems can be chosen arbitrarily, we may assume an optimal ordering. For a fixed set $ S $ of size $ k $, we can order the problems in $ S $ by increasing $ a_i $ (greedy). Then, problem $ i $ contributes a point if and only if its position in this sorted order $ \\leq a_i $.\n\nThus, for a set $ S $ of size $ k $, sort $ S $ by $ a_i $: $ a_{i_1} \\leq a_{i_2} \\leq \\dots \\leq a_{i_k} $. Then:\n$$\ns = \\sum_{j=1}^{k} \\mathbf{1}_{j \\leq a_{i_j}}\n$$\n\n**Constraints:**\n\n- $ \\sum_{i \\in S} t_i \\leq T $\n- $ S \\subseteq \\{1, 2, \\dots, n\\} $\n\n**Goal:**\n\nFind $ S \\subseteq \\{1, 2, \\dots, n\\} $ maximizing $ s $, subject to $ \\sum_{i \\in S} t_i \\leq T $, and output $ s $, $ |S| $, and the indices in $ S $.\n\n---\n\n**Formal Optimization Problem:**\n\nMaximize  \n$$\ns = \\sum_{j=1}^{|S|} \\mathbf{1}_{j \\leq a_{i_j}} \\quad \\text{where } a_{i_1} \\leq a_{i_2} \\leq \\dots \\leq a_{i_{|S|}} \\text{ for } S = \\{i_1, \\dots, i_{|S|}\\}\n$$\n\nSubject to  \n$$\n\\sum_{i \\in S} t_i \\leq T\n$$\n\n$$\nS \\subseteq \\{1, 2, \\dots, n\\}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF913D","tags":["binary search","brute force","data structures","greedy","sortings"],"sample_group":[["5 300\n3 100\n4 150\n4 80\n2 90\n2 300","2\n3\n3 1 4"],["2 100\n1 787\n2 788","0\n0"],["2 100\n2 42\n2 58","2\n2\n1 2"]],"created_at":"2026-03-03 11:00:39"}}