#include <iostream>
#include <fstream>
using namespace std;

ifstream d("rucsac.in");
ofstream o("rucsac.out");
int g,n,a[5001],b[5001],c[10001],sol;

int main()
{
    int i,j;
    d>>n>>g;
    for(i=1; i<=n; i++)
        d>>a[i]>>b[i];
    for(i=1; i<=n; i++)
        for(j=g-a[i]; j>=0; --j)
        {
            if(c[j+a[i]]<c[j]+b[i])
            {
                c[j+a[i]]=c[j]+b[i];
                if(c[j+a[i]]>sol)
                    sol=c[j+a[i]];
            }
        }
    o<<sol;
    return 0;
}