货运汽车

题目描述:

有一辆载重量为 v 的货车， 准备运送两种物品。 物品 A 的重量为 1， 物体 B 的重量为 2， 每个物品都有一个价值。 求货车可以运送物品的最大价值。

输入格式:

第一行包含两个整数 n 和 v,分别表示有 n 个物品， 货车的载重量为 v。 (1 ≤ n ≤ 10^5; 1 ≤ v ≤ 10^9)

接下来 n 行， 每行两个整数， 分别表示物品的重量 ti 和价值 pi。 , (1 ≤ ti ≤ 2; 1 ≤ pi ≤ 10000)

输出格式:

第一行， 一个整数， 表示最大价值。

第二行 按价值从大到小，价值相同按编号从小到大，输出装入汽车中重量为1的物品，多个编号用空格隔开（如果没有重量为1的物品，第二行不用输出任何信息）。

第三行 按价值从大到小，价值相同按编号从小到大，多个编号用空格隔开（如果没有重量为2的物品，第三行不用输出任何信息）。

样例输入:

3 2
1 2
2 7
1 3

样例输出:

7
2

提示:

如果能装同样价值的物品，尽量多装载重量为1的物品。

时间限制: 1000ms
空间限制: 256MB

---

来源: CodeForce