#include <cstdio>
#include <iostream>
#include <algorithm>
#define lgb 1048576
using namespace std;
FILE*f=freopen("rucsac.in","r",stdin);

int pos=0;
char buff[lgb];
int g[5001],p[5001],rez[3][10001],la,lp,i,n,G,_g;
inline void read(int &nr)
{
    while(buff[pos]<'0'||buff[pos]>'9')
        if(++pos==lgb)    fread(buff,1,lgb,stdin),pos=0;
    nr=0;
    while(buff[pos]>='0'&&buff[pos]<='9')
    {
        nr=(nr<<3)+(nr<<1)+buff[pos]-'0';
        if(++pos==lgb)
            fread(buff,1,lgb,stdin),pos=0;
    }
}
int main()
{
    freopen("rucsac.out","w",stdout);
    fread(buff,1,lgb,stdin);
    read(n);
    read(G);
    for(i=1; i<=n; i++)
        read(g[i]),read(p[i]);

    //rez
    la=1;
    lp=2;
    for(i=1; i<=n; i++)
    {
        for(_g=1; _g<=G; _g++)
        {
            rez[la][_g]=rez[lp][_g];
            if(_g>=g[i])
                rez[la][_g]=max(rez[lp][_g],rez[lp][_g-g[i]]+p[i]);
        }
        swap(la,lp);
    }
    printf("%d ",rez[lp][G]);
}