题目描述

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

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

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

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

输入格式

第一行一个整数 $n$ 和 $tot$，表示总共的物品数和背包大小。

接下来 $n$ 行，每行两个整数 $v_i$ 和 $w_i$，分别表示第 $i$ 个物品的价值和重量。

输出格式

第一行一个整数，表示最优的答案。

第二行一个整数 $x$，表示最有答案中选了 $x$ 个物品。

第三行 $x$ 个整数，按从小到大的顺序，表示物品的编号。

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

10
2
2 4

提示

并不是按字典序，看清题意。

数据范围

$n≤100$

$tot≤10^5$