当前没有测试数据。

题目描述

八（1）班由于在期中考中获得了团体第一名，班主任吴老师决定开一场庆功会。于是购买东西的任务就交给了小李同学（钱由班会出）。由于小李同学四肢发达，头脑简单，于是这个任务便落到了你头上（当然不要你跑腿。跑腿是小李的事 ^_^）注：可以全买，但不能不买。即至少买1种。

输入格式

第一行两个正整数 $n(n \le 500),m(m \le 5000)$，其中 $n$ 代表希望购买物品的种数，$m$ 表示班会拨给小李的钱数。

接下来 $n$ 行，每行 $3$ 个数，$v,w,s$ ，分别表示第 $i$ 种物品的价格、价值（注意：价格和价值是不同的概念）和购买数量（只能买 $0$ 件或 $s$ 件），其中 $v \le 100,w \le 1000,s \le 10$ 。

输出格式

输出共两行。第一行，一个整数，表示此次购买能获得的最大的价值（注意！不是价格）。第二行，小李此次购买（能获得的最大价值）所选择的物品种类的序号，序号按升序输出。

输入输出样例

5 1000 
80 20 4 
40 50 9 
30 50 7 
40 30 6 
20 20 1

1000
2 3 4 5

样例解释

输入第一行 $5$ 和 $1000$ 代表有 $5$ 种商品，最多可以花 $1000$ 元。下一行是每种物品的价格，价值和购买数量。最后的输出 $1000$ $2$ $3$ $4$ $5$ 表示最大价值是 $1000$ ，购买了第 $2$、 $3$、 $4$、 $5$ 种物品。

数据范围

见题目。