#include <fstream>
using namespace std;
ifstream f("rucsac.in");
ofstream g("rucsac.out");
#define inf 2000000000
int x,y,n,gr,w,p,v[10001],j,i;
int main()
{
    f>>n>>gr;
    for(i=1;i<=gr;i++)
        v[i]=inf;
    for(i=1;i<=n;i++){
        f>>w>>p;
        for(j=gr-w;j>=0;j--)
            if(v[j]!=inf)
               {
                    if(v[j+w]==inf)
                        v[j+w]=v[j]+p;
                    else
                        if(v[j+w]<v[j]+p)
                            v[j+w]=v[j]+p;
               }
    }
        g<<v[gr];
    return 0;
}