#include<iostream>
#include<fstream>

using namespace std;

ifstream f("rucsac.in");
ofstream g("rucsac.out");

int maxim(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

int main()
{
    int d[2][10010],i,j,n,G,w[5010],p[5010];
    f>>n>>G;
    for(i=1; i<=n; i++)
        f>>w[i]>>p[i];

    for(i=1; i<=n; i++)
        for(j=0; j<=G; j++)
            //if(w[i]>j)
            {
                d[i][j]=d[i-1][j];
            if(w[i]<=j)
            {
                d[i][j]= d[i-1][j];
                if(d[i-1][j-w[i]]+p[i] >d[i][j] )
                    d[i][j]= d[i-1][j-w[i]]+p[i];
            }

    int maxi=INT_MIN;
    for(i=0; i<=G; i++)
        if(d[n][i]>maxi)
            maxi=d[n][i];
    g<<maxi;

    return 0;
}