#include <fstream>

using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g,i,j,W[5005],P[5005],DP[2][10005],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=1-l;
        for(j=1;j<=g;j++)
        {
            DP[l][j]=DP[lp][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;
}