#include <iostream>
#include <fstream>

using namespace std;

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

int main()
{

    uint64_t n,g,weight,profit,max=0,v[10005];
    f>>n>>g;
    for (uint64_t i=0; i<n; ++i)
    {
        f>>weight>>profit;
        for (uint64_t j=g-weight; j; --j)
            if(v[j]>0)
            {
                if(v[j]+profit>v[j+weight]) v[j+weight]=v[j]+profit;
                if(v[j+weight]>max) max=v[j+weight];
            }
        if(profit>v[weight]) v[weight]=profit;
        if(v[weight]>max) max=v[weight];
    }
    t<<max;
    return 0;
}