#include <fstream>
#include <iostream>

using namespace std;

long long int n,g,w[5001],p[5001],cost[5001][10001],maxim;

int main()
{
    ifstream in("rucsac.in");
    ofstream out("rucsac.out");
    int i,j;
    in>>n>>g;
    for(i=1; i<=n; i++)
    {
        in>>w[i]>>p[i];
    }
    for(i=1; i<=n; i++)
    {
        for(j=0; j<=g; j++)
        {
            if(j+w[i]<=g)
                if(cost[i-1][j+w[i]]<cost[i-1][j]+p[i] )
                    {
                        cost[i][j+w[i]]=p[i]+cost[i-1][j];
                        if(cost[i][j+w[i]]>maxim)
                            maxim=cost[i][j+w[i]];
                    }
                else
                {
                    cost[i][j+w[i]]=cost[i-1][j+w[i]];
                }

        }
    }
    out<<maxim;
    in.close();
    out.close();
    return 0;
}