#P18678. Classical Scheduling Problem

    ID: 18014 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-二分答案枚举中间点前后缀分解堆贪心交换论证

Classical Scheduling Problem

Classical Scheduling Problem

距离一门非常重要的科目的重要考试还有t分钟。该科目共有n个不同主题,编号为1到n。学习第i个主题需要a_i分钟。

这门科目相当复杂,学过一个主题也不一定能在考试时对它有信心。要对第i个主题有信心,你必须总共学习至少b_i个主题,其中包括主题i本身。

切换学习主题不需要时间。因此,你能学完互不相同的主题p_1,p_2,…,p_k,当且仅当它们的学习时间之和不超过t。学完这些主题之后,你对其中主题p_i有信心,当且仅当k≥b_(p_i)。学习的先后顺序没有影响。

请选择考试前要学习的主题,使得最终有信心的主题数量最多。你可以学习一些最终仍没有信心的主题,以满足其他主题对总学习数的要求。

输入格式

每份输入包含多组测试。第一行包含测试组数q(1≤q≤10^4),随后依次描述各组。

每组第一行包含n和t,表示主题数和考前剩余时间(1≤n≤2×10^5,1≤t≤2×10^14)。

接下来n行,第i行包含a_i和b_i,分别表示学习第i个主题需要的分钟数,以及对该主题有信心所需的总学习主题数(1≤a_i≤10^9,1≤b_i≤n)。

保证所有测试组的n之和不超过2×10^5。

输出格式

对每组测试,先输出考试时能够有信心的主题数的最大值。

然后输出所需学习的主题数k,以及k个互不相同的整数p_1,p_2,…,p_k,表示要学习的主题原编号,顺序任意(0≤k≤n,1≤p_i≤n)。

学习总时间必须不超过t,所学k个主题中满足b_(p_i)≤k的数量必须等于你输出的最大值。如果有多种最优方案,输出任意一种。

样例输入 1

2
4 100
20 1
40 4
60 3
30 3
1 5
10 1

样例输出 1

2
3
1 2 4
0
0

样例说明

第一组可以学习主题1、2、4,耗时20+40+30=90分钟,不超过100分钟。虽然主题2要求学完4个主题,最终并没有信心,但主题1和4都满足各自条件,因此有信心的主题数为2;不可能得到更多。