#include <bits/stdc++.h>
#define N 5005

using namespace std;

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

int n, G;
int g[N], p[N];

void read()
{
    int i, j;
    fin >> n >> G;
    for ( i = 1; i <= n; ++i )
         fin >> g[i] >> p[i];
}

int rucsac()
{
    int i, j;
    int c[N][N] = {0};
    for ( i = 1; i <= n; ++i )
         for ( j = G; j >= g[i]; --j )
              c[i][j] = max( c[i-1][j], p[i] + c[i-1][j-g[i]] );
    return c[n][G];
}

int main()
{   read();
    fout << rucsac();
    return 0;
}