#include <fstream>

using namespace std;
int i,j,n,G,sol;
int v[5005],w[5005],m[10005];
int main()
{
    ifstream f("rucsac.in");
    ofstream g("rucsac.out");

    f>>n>>G;
    for(i=1;i<=n;i=i+1)
    {
        f>>w[i];
        f>>v[i];
    }

    for(i=1;i<=n;i=i+1)
    for(j=G;j>=0;j--)
        if(w[i]<j)
        m[j]=max(m[j],m[j-w[i]]+v[i]);
    g<<m[G];








    return 0;
}