#include <stdio.h>
#define max(a,b) (a)>(b)? (a):(b);

main(){
    int N,W;
    int v[100],w[100];
    int dp[2][10001]={{0,},};
    int i,j;

    scanf("%d %d",&N,&W);
    for(i=0;i<N;i++)
        scanf("%d %d",&v[i],&w[i]);

    for(i=1;i<=N;i++){
        for(j=0;j<=W;j++){
            if(j-w[i-1]<0)
                dp[i%2][j]=dp[(i-1)%2][j];
            else
                dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i-1]]+v[i-1]);
        }
    }

    int maxv=-1;
    for(i=0;i<=W;i++){
        maxv=max(maxv,dp[N%2][i]);
    }
    printf("%d\n",maxv);

    return 0;
}