#include <iostream>
#include <fstream>
using namespace std;

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

struct hot
{int g,val;};

void citire(hot v[],int &n,int &G)
{
    int i;
    fin>>n>>G;
    for(i=1;i<=n;i++)
        fin>>v[i].g>>v[i].val;
}

void gridi(hot v[],int n,int G)
{
    int d[10005],ans;
    for(int i=1;i<=n;i++)
        for(int j=g;j-v[i].g>=0;j--)
        {
            d[j]=max(d[j],d[j-v[i].g]+v[i].val);
            ans=max(ans,d[j]);
        }
    out<<ans;
}
int main()
{
    int n,G;hot v[5001];
    citire(v,n,G);
    gridi(v,n,G);
    return 0;
}