#include <stdio.h>

#define max(x, y) ((x) > (y) ? (x) : (y))

int main(void) {
    int N, W;
    int v[100], w[100];
    int dp[10001];  // dp[i] : ??????i????¶??????????????????????????????\????????¨???????????????????????§??? => dp[0] = 0
    int i, j;

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

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

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

    return 0;
}