#include<iostream>
using namespace std;

int main()
{
  int C[100][100] = {0};
  int n, W;
  int w[100], v[100];
  int newitem[100];

  cin >> n;
  cin >> W;
  register int i;
  for(i = 1; i <= n; i++)
    cin >> v[i] >> w[i];

  register int j;
  for(i = 1; i <= n; i++)
    {
      cout << "w[" << i << "]: " << w[i] <<", v[" << i << "]: " << v[i] << endl;
      for(j = 1; j <= W; j++) //重さjのナップザックについて
	/*
	  大きいナップザックの内容は、小さいナップザックの内容に追従する。
	  たとえば、大きさ2のナップザックの内容が書き換えられれば、
	  それ以降の大きさ3〜Wのナップザックの内容も書き換えられる。
	  小さいナップザックの中身は常に最大値をとるので、
	  大きいナップザックにアイテムを入れるときはそのナップザックの
	  中身は最適化されている。
	 */
	{
	  if(w[i] > j)//アイテムiが入らない場合
	    {
	      C[i][j] = C[i - 1][j];
	      continue;
	    }
	  /*
	    値の説明:

	    C[i - 1][j]
	    大きさjのナップザックに、アイテム1からアイテムi - 1まで
	    で最適なものを入れたときの価値の合計

	    C[i - 1][j - w[i]] + v[i]
	    大きさj - （アイテムiの大きさ）の
	    ナップザックにアイテムiを入れたときの価値の合計

	    このif-else文では、アイテムiを選択するかしないかを決めている。

	    newitem[j]
	    ナップザックが大きさjになったとき、入れられたアイテムの添字
	  */
	  if(C[i - 1][j] > C[i - 1][j - w[i]] + v[i]) //アイテムを選択しない（入らないも含む）場合
	    C[i][j] = C[i - 1][j];
	  else 
	    {
	      C[i][j] = C[i - 1][j - w[i]] + v[i];
	      newitem[j] = i;
	    }
	  cout << "C[" << i << "][" << j << "]: " << C[i][j] << endl;
	  
	}
    }

  int maxv = 0;
  for(i = 1; i <= n; i++)
    if(C[i][W] > maxv) maxv = C[i][W];

  for(i = W; i >= 1; i -= w[newitem[i]])
    cout << "品物: " << newitem[i] << "...重さ: " << w[newitem[i]] << ", 価値: " << v[newitem[i]] << endl;

  cout << "result: " << maxv << endl;

  return 0;
}