#include <bits/stdc++.h>
#define NMAX 5000
#define NRMAX 10000
using namespace std;
ifstream fin( "rucsac.in" );
ofstream fout( "rucsac.out" );
int v[NMAX + 1];
int c[NMAX + 1];
int dp[NRMAX + 1];
int main() {
    int n, g, i, j;
    fin >> n >> g;
    for( i = 0; i < n; i++ )
      fin >> c[i] >> v[i];
    for( i = 0; i < n; i++ )
      for( j = g; j > 0; j-- )
        if( c[i] <= j )
          dp[j] = max( dp[j], dp[j - c[i]] + v[i] );
    fout << dp[g];
    return 0;
}