#include<iostream.h>
//////////////////////////////////////////////////////////////////////////
//背包三
//有價值分別為x1 x2 x3  x4  x5...xt (t<100 && xi(int))金屬,
//體積為y1 y2  y3  y4...yt (yi(int))個單位且金屬不可以分割
//有一個背包大小為t個單位(t<100)
//求背包能裝的金屬的最大的價值
//動態(tài)規(guī)劃法
////////////////////////////////////////////////////////////////////////////////
struct metal
{
	int value;
	int volume;
};

metal metal_group[100];

int pp[110][110];//x個單位體積的背包在前y個金屬中可以獲得的最大價值pp[x][y]

int cal_metal_value();

int cal_metal_value()
{
	int n,t;
	cout<<"put in the number of kind of the metal and the total volume"<<endl;
    cin>>n>>t;
	cout<<"put in each metal's value and volume"<<endl;
	for (int r=1;r<=n;r++)
	    cin>>metal_group[r].value>>metal_group[r].volume;

    for(int i=1;i<=t;i++)
	   for(int j=1;j<=n;j++)
		   if((metal_group[j].volume<=i)
			   &&metal_group[j].value+pp[i-metal_group[j].volume][j-1]>pp[i][j-1])
			   pp[i][j]=metal_group[j].value+pp[i-metal_group[j].volume][j-1];
		   else
			   pp[i][j]=pp[i][j-1];
	return pp[t][n];
}


void main()
{
	cal_metal_value();
}