D31s9. 装物品方案（小内存） 时间限制：2.0s 内存限制：16.0MB Special Judge 代码提交间隔：5分钟(现在可以提交) 问题描述 有n件物品，第i件物品的重量为wi（整数）。

对于给定的整数 ， 请选择一些物品，使得拼出的重量不超过 ，请问在此前提下能拼出的最大重量是多少？具体的方案是怎样的？

输入格式 输入的第一行包含一个整数 ，表示物品数量。

第二行包含n个整数w1,w2…wn分别为每个物品的重量。

最后一行包含一个整数 。

输出格式 输出的第一行包含一个整数T，表示答案。

第二行包含一个整数c，表示要选择的物品个数。

第三行包含c个整数，为每个选择的物品的编号，按照从小到大的顺序输出，相邻整数之间使用一个空格分隔。

样例输入 3 4 4 6 12 Data 样例输出 10 2 1 3 Data 以下答案也正确

10 2 2 3

这道背包问题我一开始打算用回溯做，但会超时和错误，现在打算还是老老实实用背包做，请各方神圣帮本蒟蒻看看吧！

急！在线蹲答案！

悬赏10个赞！