#include <stdio.h>
#include <stdlib.h>

int max2(int x, int y) {

    return x > y ? x : y;
}

// ??????b??????????????????????????????0???n?????\??????????????????????????§???
int m(int b, int n, int *v, int *w) {
    int i;

    if( n < 0 ) return 0;
    if( b < w[n] ) return m(b, n - 1, v, w);

    return max2(m(b, n - 1, v, w), m(b - w[n], n - 1, v, w) + v[n]);
}

int main(void) {
    int N, W;
    int *v, *w;
    int i;

    scanf("%d %d", &N, &W);

    v = (int *)malloc(sizeof(int) * N);
    w = (int *)malloc(sizeof(int) * N);

    for( i = 0; i < N; i++ ) {
        scanf("%d %d", v + i, w + i);
    }

    printf("%d\n", m(W, N - 1, v, w));

    free(v);
    free(w);

    return 0;
}