#include <iostream>
#include <fstream>

using namespace std;

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

struct obiect
{
    int w,p;
}v[5001];

int s[10001],n,G;

void citire ()
{
    f>>n>>G;
    for(int i=1;i<=n;i++)
        f>>v[i].w>>v[i].p;
}

void dinamica()
{
    int i,j;
    for(i=1;i<=n;i++){
        for(j=G;j>=v[i].w;j--){
            s[j]=max(s[j],s[j-v[i].w]+v[i].p);
        }
    }
}

int main()
{
    citire();
    dinamica();
    g<<s[G];
return 0;
}