//#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct elem
{
    int kg,ar;
};

struct rez
{
    int ar;
    vector <int> v;
};

elem t[5001];

rez x[5001][10001];

int i,j,n,g,maxi;

int main()
{
    cin>>n>>g;
    for(i=1;i<=n;++i)
        cin>>t[i].kg>>t[i].ar;

    x[1][t[1].kg].ar=t[1].ar;
    x[1][t[1].kg].v.push_back(1);

    for(i=2;i<=n;++i)
    {
        if(t[i].kg<=g)
        {
            if(x[i-1][t[i].kg].ar<t[i].ar)
            {
                x[i][t[i].kg].ar=t[i].ar;
                x[i][t[i].kg].v.push_back(i);
            }
            for(j=g;j>=1;--j)
            {
                if(x[i-1][j].ar!=0)
                {
                    x[i][j]=x[i-1][j];
                    if(j+t[i].kg<=g&&x[i-1][j+t[i].kg].ar<x[i-1][j].ar+t[i].ar)
                    {
                        x[i][j+t[i].kg].ar=x[i-1][j].ar+t[i].ar;
                        x[i][j+t[i].kg].v=x[i-1][j].v;
                        x[i][j+t[i].kg].v.push_back(i);
                    }
                    else
                    {
                        x[i][j+t[i].kg]=x[i-1][j+t[i].kg];
                    }
                }
            }
        }
    }

    maxi=0;
    for(i=1;i<=g;++i)
        if(x[n][i].ar>maxi) maxi=x[n][i].ar;

    cout<<maxi;

    return 0;
}