CF 3B

Lorry

Description

有一个旅游团要去进行一个皮艇和双体船（形式两个皮艇绑在一起的船）的旅行。他们租借了一辆大货车来到船仓，要将皮艇和双体船运送到目的地。已知所有的皮艇形状和体积都相同（全部占一立方米），所有的双体船形状和体积也都相同，但都是皮艇的两倍（全部占两立方米）。

每艘船都有自己的载重量，即使他们看起来一模一样，载重量也会各有不同。知道货车车厢的容积和每艘船的类型（皮艇或双体船）、载重量，请计算出货车应该运送哪些船，能使得载重量总和最大。我们假设货车车厢的空间总是能够有效利用，也就是说，只要总体积不超过车厢的容积，就可以将小船放入车厢，不用考虑形状因素。

Input

第一行包含一对整数 n 和 v (2 ≤ n ≤ 10⁵; 1 ≤ v ≤ 10⁹)，n 表示船仓中船的数量，v 表示货车车厢的体积。以下 n 行表示每艘船的信息，每行包含一对整数 t_i 、 p_i (1 ≤ t_i ≤ 2; 1 ≤ p_i ≤ 10⁴)， t_i 表示船的类型（1 是皮艇，2 是双体船），p_i 是船的载重量。每艘船按输入的顺序从 1 到 n 编号。

Output

第一行输出最大载重量总和。第二行输出要达到该最大载重量总和，需要运送哪些船，输出这些船的编号。

Solution

一开始最容易想到的就是简单的 01 背包，当然只要仔细一看，就知道不必搞得那么复杂，并且 n 较大，复杂度也达不到要求。

我们只需要将性价比尽量高（载重量尽量大，体积尽量小）的船放入车厢中就可以了，由于船只有两种，我们可以用替代法来做。

具体的做法是，把所有船按类型分成两类，并且分别排序，载重量大的船要优先放。先把所有皮艇放到车厢中，然后试图用载重量最大的双体船和当前车厢内载重量最小的两艘皮艇比较，如果载重量比俩皮艇载重量之和还大，就取出两艘皮艇，放入一艘双体船。

需要特别注意的是，放双体船的时候，要考虑车厢体积是否已放满。另外在和剩下体积为 1 时，只需要取出一艘皮艇就可以放入一艘双体船。