#include <fstream>
#include <iostream>
#define Nmax 5005
#define Wmax 10005

using namespace std;

string file="rucsac";

ifstream f( (file + ".in").c_str() );
ofstream g( (file + ".out").c_str() );

int n, G;
struct knp{
int w, v;
}a[Nmax];

//int dp[Nmax][Wmax];
int dp[2][Wmax];
int main()
{
    f >> n >> G;
    for (int i = 1; i <= n; i++)
        f >> a[i].w >> a[i].v;
    //dp[i][j]=profitul maxim luand din primele i obiecte cu gr j
    int l=0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= G; j++)
        {
            dp[1-l][j]=dp[l][j];
            if(j-a[i].w < 0) continue;
            dp[l][j]=max(dp[1-l][j], dp[1-l][j-a[i].w]+a[i].v);
        }

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