#include <fstream>

using namespace std;

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

#define N 5000

struct obiect{
    int greutate, pret;} v[N+1];

int g[2*N+1], n, G, sol;

int main()
{
    in >> n >> G;

    for(int i=1; i<=n; i++)
        in >> v[i].greutate >> v[i].pret;

    for(int i=1;i<=n;i++)
    {
        for(int j=G-v[i].greutate; j>=0; j--)
        {
            g[j+v[i].greutate] = max(g[j]+v[i].pret, g[j+v[i].greutate]);
            if(g[j+v[i].greutate] > sol)
                sol = g[j+v[i].greutate];
        }
    }

    out << sol;

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