#include <iostream>
#include <fstream>
#define nmax 10005
#define inf (1<<30)
using namespace std;

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

int main()
{

    int n,g,a[nmax], b[nmax],w,p;
    int *first, *second,*aux;

    first=a;
    second=b;

    f>>n>>g;


    for(int i=0; i<=g; i++)
    {
        *(first+i)= 0;
    }


    for(int i=1; i<=n; i++)
    {
        f>>w>>p;
        for(int j=1; j<w; j++) *(second+j)=*(first+j);
        for(int j=w; j<=g; j++) *(second+j)=max(*(first+j-w)+p, *(first+j));
        aux=first;
        first=second;
        second=aux;
    }

    go<< *(first+g);


    return 0;
}