#include <fstream>

using namespace std;

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

struct ob
{
    int g,c;
};

ob a[5001];
int n,G,Max,l[10001];

void pd()
{
    int i,j;
    for(i=1; i<=G; i++)
    {
        for(j=Max; j>=0; j--)

            if(l[j]!=-1)

                l[j+a[i].g]=l[j]+a[i].c;

        Max+=a[i].g;
    }
}


int main()
{
    int i;
    fin>>n>>G;
    for(i=1; i<=n; i++)
    {
        fin>>a[i].g>>a[i].c;
        l[i]=-1;
    }
    l[0]=0;
    pd();
    for(i=1; i<=G; i++)
        if(Max<l[i])Max=l[i];
    fout<<Max;


    return 0;
}