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

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

struct fsdfn{
int w, p;
}v[Nmax];

int dp[2][10005];
int n, G;

int main()
{
    f >> n >> G;
    for (int i = 1; i <= n; i++)
    {
        f >> v[i].w >> v[i].p;
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = G; j >= 0; j--)
            if(j >= v[i].w) dp[i%2][j]=max(dp[(i-1)%2][j], dp[(i-1)%2][j-v[i].w]+v[i].p);
        else dp[i%2][j]=dp[(i-1)%2][j];
    }

    g << dp[n%2][G];
    return 0;
}