#include <fstream>

using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,i,j,W[5001],P[5001],DP[2][10001],l,lp;
int main()
{
    fi>>n>>g;
    for(i=1;i<=n;i++)
        fi>>W[i]>>P[i];
    for(i=1;i<=n;i++)
    {
        l=i%2;
        lp=(i-1)%2;
        for(j=1;j<=g;j++)
            if(W[i]<=j)
                DP[l][j]=max(DP[lp][j],DP[lp][j-W[i]]+P[i]);
    }
    fo<<DP[n%2][g];
    fi.close();
    fo.close();
    return 0;
}