#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n,i,j,dp[3][10001],g,w[5001],p[5001];
void mut()
{
    for(int x=1;x<=g;x++)
        dp[1][x]=dp[2][x];
}
int main()
{
    fin>>n>>g;
    for(i=1;i<=n;i++)
        fin>>w[i]>>p[i];
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=g;j++)
        {
            if(j-w[i]>=0)
            dp[2][j]=max(dp[1][j],dp[1][j-w[i]]+p[i]);
            else
                dp[2][j]=dp[1][j];
        }
        mut();
    }
    fout<<dp[2][g];
    return 0;
}