1857: 可持久化01背包
文件提交：无需freopen
内存限制：512 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：0
解决：0
题目描述
baobao学习了很多可持久化数据结构，例如可持久化线段树、可持久化平衡树、可持久化并查集.......
今天，baobao翻了一下pcf的博客，发现里面有个可持久化01背包的问题。他很乐意与你分享。
这个01背包问题只是在原有的基础上增加了查询功能。即在输出最优解后，还要输出选择了那些数。
同时，在这个问题中你必须得按顺序加入物品，若加入这个物品不会使当前答案变优，你就不应该记录下这个物品。
今天，baobao翻了一下pcf的博客，发现里面有个可持久化01背包的问题。他很乐意与你分享。
这个01背包问题只是在原有的基础上增加了查询功能。即在输出最优解后，还要输出选择了那些数。
同时，在这个问题中你必须得按顺序加入物品，若加入这个物品不会使当前答案变优，你就不应该记录下这个物品。
输入
第一行一个整数n和tot，表示总共的物品数和背包大小。(n≤100,tot≤100,000)
接下来n行，每行两个整数vi和wi，分别表示第i个物品的价值和重量。
【输出要求】
第一行一个整数，表示最优的答案。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。
【输入样例】
【输出样例】
【解题提示】
接下来n行，每行两个整数vi和wi，分别表示第i个物品的价值和重量。
【输出要求】
第一行一个整数，表示最优的答案。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。
【输入样例】
【输出样例】
【解题提示】
输出
第一行一个整数，表示最优的答案。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。
第二行一个整数x，表示最有答案中选了x个物品。
第三行x个整数，按从小到大的顺序，表示物品的编号。
样例输入
5 12
1 2
3 4
5 6
7 8
9 10样例输出
10
2
2 4提示
并不是按字典序，看清题意。