#include <cstdio>
#include <algorithm>

using namespace std;

int v[10005],v2[10005],v3[10005];

int main()
{
    FILE *fin,*fout;
    int n,g,x,i,j,nr;
    fin=fopen("rucsac.in","r");
    fout=fopen("rucsac.out","w");
    fscanf(fin,"%d%d", &n, &g);
    nr=0;
    for (i=1;i<=n;++i)
        fscanf(fin,"%d%d", &v[i], &v2[i]);
    for (i=1;i<=n;i++) {
        for (j=g-v[i];j>=0;j--) {
            x=j+v[i];
            v3[x]=max(v3[x],v3[j]+v2[i]);
            nr=max(nr,v3[x]);
        }
    }
    fprintf(fout,"%d\n", nr);
    return 0;
}