#include <bits/stdc++.h>
#define L 5005
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
long long w[L], p[L], dp[L];
int main(){
  long long n, g, i, x, ans = 0;
  fin >> n >> g;
  for (i = 1; i <= n; i++)
    fin >> w[i] >> p[i];
  for (i = 1; i <= n; i++)
    for (x = g; x >= w[i]; x--){
      dp[x] = max(dp[x], dp[x - w[i]] + p[i]);
      ans = max(ans, dp[x]);
    }
  fout << ans << "\n";
  return 0;
}