#include <fstream>

using namespace std;

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

int castig[5001], n, gr[5001],c[5001], G, sol;

int main()
{
    in>>n>>G;
    for(int i=1; i<=n; i++)
        in>>gr[i]>>c[i];

    for(int i=1; i<=n; i++)
        for(int j=G-gr[i]; j>=0; j--)
        {
            if(castig[j+gr[i]] < castig[j]+c[i])
            {
                castig[j+gr[i]] = castig[j]+c[i];
                if(castig[j+gr[i]] > sol)
                    sol = castig[j+gr[i]];
            }

        }

    out<<sol;
    return 0;
}