#include <bits/stdc++.h>
using namespace std;
const int NMAX = 5e3+2;
const int VMAX = 1e4+2;
int n,g,dp[2][VMAX],w[NMAX],p[NMAX];

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

template<typename T>
void maxSelf(T &a, T b){
  a = max(a, b);
}

int main() {
  fin >> n >> g;
  for(int i = 1; i <= n; i++){
    fin >> w[i] >> p[i];
  }
  for(int i = 1; i <= n; i++){
    int prev = (i-1)&1, curr = !prev;
    memcpy(dp[curr], dp[prev], sizeof(dp[curr]));
    for(int j = 0; j <= g-w[i]; j++){
      maxSelf(dp[curr][j+w[i]], dp[prev][j] + p[i]);
    }
  }
  fout << dp[n&1][g];
  return 0;
}