#include <fstream>
#include <iostream>

using namespace std;

#ifdef INFOARENA
#define cout fout
#endif // INFOARENA

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

#define limg 10001
#define limn 5001
int N,G,a[limn][limg];
int gr[limn],p[limn];


int main()
{
    int i,j;
    fin>>N>>G;

    for(i=1; i<=N; i++)
        fin>>gr[i]>>p[i];

    for(i=1; i<=N; i++)
        for(j=0; j<=G; j++)
        {
             if(gr[i]<=j)
                a[i][j]=max( a[i-1][j] , a[i-1][j-gr[i]]+p[i] );
             else
                a[i][j]=a[i-1][j];

        }

    fout<<a[N][G];


    return 0;
}