题目描述

给你 $n$ 个物品，每个物品的体积是 $w_i$，价值是 $v_i$。每个物品只能选择一次。

有一个容量为 $m$ 的背包，问选择哪些物品装入进背包使得不超过背包容量的前提下，装入背包的价值最大。

输入格式

第一行输入 $n$ 和 $m$。

接下来 $n$ 行，每行输入两个整数分别为 $w_i,v_i$。

输出格式

第一行输出一个整数代表最大价值。

接下来一行输入若干个空格隔开的数字，代表选择的物品的编号。要求从小到大输出被选择的物品的编号。

如果答案有多组解，你可以输出任意一组。这意味着本题具有 SPJ。

3 6
1 3
5 4
6 7

7
1 2

提示

样例解释

输出 3 或 1 2 都算正确。

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 10^3$，$1\leq w_i,v_i\leq 1000$。