← 返回题目列表

Codeforces · 3/B

B. 货车

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

一群游客要去皮划艇和双体船游览。一辆租来的卡车已抵达船库,可将皮划艇和双体船运至出发点。众所周知,所有皮划艇的尺寸相同(每艘占用1立方米的空间),所有双体船的尺寸相同,但比皮划艇大两倍(占用2立方米的空间)。

每个水上车辆都有特定的承载能力,应该注意的是,看起来相同的水上车辆可能具有不同的承载能力。已知卡车车体体积和船库内的水上车辆清单(每种车辆的类型和载重量已知),找出卡车可以容纳的、总载重量最大的一组车辆。卡车的车体容积得到有效利用,也就是说您可以随时在卡车上放入占用空间不超过车体剩余空间的水上车辆。

输入

第一行包含一对整数 n 和 v (1 ≤ n ≤ 105; 1 ≤ v ≤ 109),其中 n 是船库中的水上车辆数量,v 是卡车车体体积,以立方米为单位。接下来的 n 行包含了水上交通工具的信息,即一对数字 ti, pi (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 104),其中 ti 是交通工具类型(1 – 皮划艇,2 – 双体船),pi 是其承载能力。水上交通工具按照其在输入文件中出现的顺序进行枚举。

输出

在第一行打印该组的最大可能承载能力。在第二行中打印一个字符串,其中包含构成最佳集合的车辆数量。如果答案不唯一,请打印其中任何一个。

示例

输入 #1

3 2
1 2
2 7
1 3

输出 #1

7
2