您正在准备调度理论考试。考试将持续 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 毫秒内解决这两个问题,并微笑着把你的答案交给老师。