← 返回题目列表

Codeforces · 913/D

D. 太简单的问题

中文机器翻译题面 查看原题

您正在准备调度理论考试。考试将持续 T 毫秒,并包含 n 个问题。您可以在精确的 ti 毫秒内解决问题 i,也可以忽略它并且不花时间。解决问题后你也不需要时间休息。

不幸的是,您的老师认为某些问题对您来说太简单了。因此,他为每个问题 i 分配了一个整数 ai,这意味着只有在您总共解决了不超过 ai 个问题(包括问题 i)的情况下,问题 i 才能为您带来最终分数。

正式来说,假设您在考试期间解决了问题 p1, p2, ..., pk。然后,您的最终得分 s 将等于 j 介于 1 和 k 之间且 k ≤ apj 的值的数量。

你已经猜到了,真正的考试第一题已经摆在你的面前了。因此,您希望提前选择一组要在考试期间解决的问题,以最大化您的最终分数。不要忘记考试的时间是有限的,你必须有足够的时间来解决所有选择的问题。如果存在不同的问题集导致最终得分最高,则其中任何一个都可以。

输入

第一行包含两个整数 n 和 T (1 ≤ n ≤ 2·105; 1 ≤ T ≤ 109) - 分别是考试中的问题数量和考试时长(以毫秒为单位)。

接下来的 n 行每行包含两个整数 ai 和 ti (1 ≤ ai ≤ n; 1 ≤ ti ≤ 104)。问题从 1 到 n 编号。

输出

在第一行中,输出一个整数 s — 您可能的最大最终分数。

在第二行中,输出一个整数 k (0 ≤ k ≤ n) — 您应该解决的问题数量。

在第三行中,输出 k 个不同的整数 p1, p2, ..., pk (1 ≤ pi ≤ n) - 您应该解决的问题的索引,以任意顺序。

如果存在多个最佳问题集,则可以输出其中任何一个。

示例

输入 #1

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

输出 #1

2
3
3 1 4

输入 #2

2 100
1 787
2 788

输出 #2

0
0

输入 #3

2 100
2 42
2 58

输出 #3

2
2
1 2

注意

在第一个示例中,您应该解决问题 3、1 和 4。在这种情况下,您将花费 80 + 100 + 90 = 270 毫秒,在考试长度 300 毫秒内(甚至给自己留出 30 毫秒休息时间)。问题 3 和问题 1 都会为您带来一分,而问题 4 则不会。你会得到两分。

在第二个示例中,考试的长度灾难性地不足以解决单个问题。

在第三个例子中,你有足够的时间在 42 + 58 = 100 毫秒内解决这两个问题,并微笑着把你的答案交给老师。