#include<stdio.h>
#define inf 99999999
int dp[10100][10100];

int max( int a , int b )
{
    if(a>b)return a;
    else return b;
}

int main(void)
{
    int N,W,v[10100],w[10100],i,j,M=0;
    scanf("%d %d",&N,&W);
    for(i=0;i<N;i++)scanf("%d %d",&v[i],&w[i]);
    dp[0][0]=0;
    for(i=1;i<N;i++)dp[0][i]=-inf;
    for(i=1;i<=N;i++){
        for(j=0;j<=W;j++){
            if(j-w[i-1]>=0)dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
            else dp[i][j] = dp[i-1][j] ;
        }
    }
    /*for(i=0;i<=N;i++){
        for(j=0;j<=W;j++){
            printf("%d\n",dp[i][j]);
        }

    }*/

        for(j=0;j<=W;j++){
            M=max(dp[N][j],M);
        }
    printf("%d\n",M);

    return 0;
}