#include <fstream>

using namespace std;

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

int n, g;
int d[5005][10005];

struct obiect
{
    int w;
    int p;
};

obiect v[5005];

int main()
{
    in >> n >> g ;
    for(int i=1; i<=n; i++)
    {
        in >> v[i].w >> v[i].p ;
    }
    for(int i=1; i<=n; i++)
    {
        for(int gr=0; gr<=g; gr++)
        {
            d[i][gr] = d[i-1][gr] ;
            if(v[i].w <= gr)
                d[i][gr] = max(d[i][gr], d[i-1][gr-v[i].w] + v[i].p) ;
        }
    }
    out << d[n][g] ;
    return 0;
}