#include <stdio.h>
typedef long long ll;
#define rep(i,n) for(ll i=0; i<(ll)(n); i++)
#define max(l,r) ((l)>(r)?l:r)

int dp[105][10101] = {0};
int main(){
    int N, W;
    scanf("%d%d", &N, &W);
    int v[105], w[105];
    rep(i, N) scanf("%d%d", v+i, w+i);

    rep(i, N){
        rep(j, W+1){
            if(j - w[i] >= 0){
                dp[i+1][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
            }else{
                dp[i+1][j] = dp[i][j];
            }
        }
    }

    printf("%d\n", dp[N][W]);
}
