2423: 可持久化01背包

baobao学习了很多可持久化数据结构，例如可持久化线段树、可持久化平衡树、可持久化并查集.......


今天，baobao翻了一下pcf的博客，发现里面有个可持久化01背包的问题。他很乐意与你分享。


这个01背包问题只是在原有的基础上增加了查询功能。即在输出最优解后，还要输出选择了那些数。


同时，在这个问题中你必须得按顺序加入物品，若加入这个物品不会使当前答案变优，你就不应该记录下这个物品。

第一行一个整数n和tot，表示总共的物品数和背包大小。(n≤100,tot≤100,000)
接下来n行，每行两个整数vi和wi，分别表示第i个物品的价值和重量。
【输出要求】
第一行一个整数，表示最优的答案。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。
【输入样例】


【输出样例】


【解题提示】

第一行一个整数，表示最优的答案。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。

5 12
1 2
3 4
5 6
7 8
9 10

10
2
2 4