//0-1 Knapsack problem 
#include <iostream>
#include <vector>
using std::cout;
using std::vector;
using std::cin;
using std::endl;

#define MAX_KNAPSACK 10
#define MAX_CONTAIN 50

class KPC
{
private:
	int v[MAX_KNAPSACK];//Value
	int w[MAX_KNAPSACK];//Weight
	int f[MAX_KNAPSACK][MAX_CONTAIN];//Best Value
	vector<int> item[MAX_KNAPSACK][MAX_CONTAIN];//Item List
	int c;//Contain
	int n;//Item Size
public:
	void DP();//物品起始号，当前容量
	void PrintVector(vector<int> vect);//打印某一格的物品清单
};

void KPC::PrintVector(vector<int> vect)
{
	if(vect.begin() == vect.end()) return;
	vector<int>::iterator it;
	for(it=vect.begin(); it!=vect.end()-1; it++)
	{
		cout << *it;
		cout << ".";
	}
	cout << *it;
}

void KPC::DP()
{
	cin >> n >> c;//先输入物品数，然后是容量
	for(int i=0; i!=n; i++)
	{
		cin >> w[i] >> v[i];//先重量，后价值
	}

	//初始化的值将作为基点
	//空的部分
	int min = w[n-1] < c ? w[n-1] : c;
	int j=0;
	for(; j<min; j++)
	{
		f[n-1][j] = 0;
	}
	//有物部分的第一行
	for(; j<=c; j++)
	{
		f[n-1][j] = v[n-1];
		item[n-1][j].push_back(n-1);
	}

	for(int j = 0; j <= c; j++)//按上到下、左到右顺序填表
	{
		for(int i=n-2; i>=0; i--)//总质量一定，找到最优值
		{
			if(j < w[i])
			{
				for(int t=j; t<=w[i]; t++)
				{
					f[i][t] = f[i+1][j];
					item[i][j] = item[i+1][j];//继承
				}
			}
			else//j == w[i]
			{
				if(f[i+1][j] > f[i+1][j-w[i]] + v[i])
				{
					f[i][j] = f[i+1][j];
					item[i][j] = item[i+1][j];//继承
				}
				else
				{
					f[i][j] = f[i+1][j-w[i]] + v[i];
					item[i][j] = item[i+1][j-w[i]];
					item[i][j].push_back(i);//添加新物品
				}
			}
		}
	}

	//输出右下角的值作为最大价值的解
	cout << f[0][c] << endl;
	//物品的解
	PrintVector(item[0][c]);
	cout << endl;
	//打印填好的价值表
	for(int i=n-1; i>=0; i--)
	{
		for(int j=0; j<=c; j++)
		{
			cout << f[i][j] << " ";
		}
		cout << endl;
	}
	cout << "-------------------" << endl;
	//打印填好的物品表
	for(int i=n-1; i>=0; i--)
	{
		for(int j=0; j<=c; j++)
		{
			cout << "[";
			PrintVector(item[i][j]);
			cout << "]";
		}
		cout << endl;
	}
}

int main()
{
	KPC KP;
	KP.DP();
	system("pause");
}