#include<cstdio>
int castig[1001],cost[1001],mat[1001][5001];
int max(int x,int y){
    if(x>y)
        return x;
    else
        return y;
        }
int main(){
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int x,y,s=0,i,j,g,w,min=99999999,sol;
    scanf("%d%d",&g,&w);
    for(i=1;i<=g;i++){
        scanf("%d%d",&cost[i],&castig[i]);
        s+=cost[i];
    }
    for(i=cost[1];i<=w;i++)
        mat[1][i]=castig[1];
    for(i=2;i<=g;i++)
        for(j=1;j<=s;j++){
            x=mat[i-1][j];
            if(j-cost[i]>0){
                y=mat[i-1][j-cost[i]]+castig[i];
                mat[i][j]=max(x,y);
            }
            else
                mat[i][j]=mat[i-1][j];
        }
    for(i=w;i<=s;i++)
        if(mat[g][i]>=w){
            printf("%d",mat[g][i]);
            break;}
    return 0;
}