#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,G,w[5005],c[5005],dp[5][10005];
int main()
{
    fin>>n>>G;
    for(int i=1;i<=n;i++)
    {
        fin>>w[i]>>c[i];
    }
    memset(dp, 0, sizeof(dp));

    for(int k=0;k<=G;k++)
            if(k>=w[1])
                dp[1][k]=max(dp[0][k], dp[0][k-w[1]]+c[1]);
            else dp[1][k]=dp[0][k];

    for(int i=2;i<=n;i++)
    {
        for(int k=0;k<=G;k++)
            if(k>=w[i])
                dp[2][k]=max(dp[1][k], dp[1][k-w[i]]+c[i]);
            else dp[2][k]=dp[1][k];
        for(int k=0;k<=G;k++)
            swap(dp[1][k],dp[2][k]),dp[2][k]=0;
    }
    fout<<dp[1][G];
    return 0;
}