#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

int d[10005],w[10005],p[10005];

int main(void){
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);
    int n,g,dr,r=0;
    scanf("%d%d",&n,&g);
    for(int i=0; i<n; ++i)
        scanf("%d%d",&w[i],&p[i]);
    memset(d,0xFF,sizeof(d));
    d[0]=0;
    dr=0;
    for(int i=0; i<n; ++i){
        for(int j=dr;j>=0;--j){
            if(d[j]!=-1 && j+w[j]<=g){
                d[j+w[i]]=max(d[j+w[i]],d[j]+p[i]);
                dr=max(dr,j+w[i]);
            }
        }
    }
    for(int i=1; i<=g; ++i)
        r=max(d[i],r);
    printf("%d",r);
    return 0;
}