#include <stdio.h>

#define MN 5001
#define MG 10001

int N, G, i, j;

int W[MN], P[MN];
int data[MN][MG];

int max(int x, int y) {
    return x > y ? x : y;
}

int main() {
    freopen("rucsac.in","r",stdin);
    freopen("rucsac.out","w",stdout);

    scanf("%d %d", &N, &G);
    for (i=1;i<=N;i++) {
        scanf("%d %d", &W[i], &P[i]);
    }

    for (i=0;i<=N;i++)
        data[i][0] = 0;
    for (i=0;i<=G;i++)
        data[0][i] = 0;

    for (i=1;i<=N;i++) {
        for (j=0;j<=G;j++) {
            data[i][j] = data[i - 1][j];
            if (W[i] <= j) {
                data[i][j] = max(data[i][j], data[i - 1][j-W[i]] + P[i]);
            }
        }
    }

    printf("%d\n", data[N][G]);

    return 0;
}