#include <iostream>
#include <fstream>
using namespace std;
#define nmax 5010

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

int n,smax,gmax,g[nmax],v[nmax],dp[2][nmax];

int main()
{
    f>>n>>gmax;
    for (int i=1; i<=n; ++i)
        f>>g[i]>>v[i];
    for (int i=1; i<=n; ++i)
    {
        for (int j=0; j<=gmax; ++j)
            if (g[i]>j)
                dp[1][j]=dp[0][j];
            else
                dp[1][j]=max(dp[0][j],dp[0][j-g[i]]+v[i]);
        for (int z=0; z<=gmax; ++z)
            dp[0][z]=dp[1][z];
    }
    w<<dp[0][gmax];
    return 0;
}