#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
const int GMAX=10005;
int n,G,w,p,dp[2][GMAX];
int main()
{
    f>>n>>G;
    int lin=1;
    for(int i=1;i<=n;i++,lin=1-lin)
    {
        f>>w>>p;
        for(int j=0;j<=G;j++)
        {
            dp[lin][j]=dp[1-lin][j];
            if(j-w>=0)
                dp[lin][j]=max(dp[lin][j],dp[1-lin][j-w]+p);
        }
    }
    lin=1-lin;
    int sol=0;
    for(int j=0;j<=G;j++)
        sol=max(sol,dp[lin][j]);
    g<<sol<<"\n";
    return 0;
}