#include <bits/stdc++.h>
#define DimMax 5000
#define ValMax 10000
#define LinMax 2

using namespace std;

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

int n, G;
int w[DimMax + 1], p[DimMax + 1];
int dp[LinMax][ValMax + 1];
int l;

int main()
{
    fin >> n >> G;
    for ( int i = 1; i <= n; i++ )
        fin >> w[i] >> p[i];

    dp[1][w[1]] = p[1];
    for ( int i = 1; i <= n; i++,l = (l + 1) % 2 )
        for ( int j = 1; j <= G; j++ )
            dp[l][j] = max(dp[l ^ 1][j], dp[l ^ 1][max(0, j - w[i])] + p[i]);

    fout << dp[l][G];
    return 0;
}