#include <bits/stdc++.h>

using namespace std;

ifstream fin ("rucsac.in");
ofstream fout("rucsac.out");

const int N_MAX = 5000 + 5, G_MAX = 10000 + 5;

int inherited, n, g, dp[N_MAX][G_MAX], wt[N_MAX], val[N_MAX];

int main(){
  fin >> n >> g;
  for(int i = 1; i<=n; ++i)
    fin >> wt[i] >> val[i];

  for(int j = 1; j<=g; ++j)
  if(j >= wt[1])
      dp[1][j] = val[1];
    else
      dp[1][j] = 0;

  for(int i = 2; i<=n; ++i)
    for(int j = 1; j<=g; ++j)
      if(j - wt[i] > 0)
        dp[i][j] = max(dp[i-1][j], dp[i-1][j - wt[i]] + val[i]);
      else
        dp[i][j] = dp[i-1][j];

  fout << dp[n][g];
	return 0;
}

//Andrei Muntean, 2018