#include <iostream>
#include <fstream>
int dp[5001][10001] = {0};
std::ifstream gin("rucsac.in");
std::ofstream gout("rucsac.out");
int main()
{
    int N,G;
    gin>>N>>G;

    for(int i=1; i<=N; i++)
    {
        int w,p;
        gin>>w>>p;

        for(int g=0; g<w; g++)
        {

            dp[i][g]=dp[i-1][g];
        }
        for(int g=w; g<=G; g++)
        {
            dp[i][g]=std::max(dp[i-1][g],dp[i-1][g-w]+p);
        }
    }

    gout<<dp[N][G];
    return 0;
}