#include <algorithm>
#include <stdio.h>

#define MaxN 5005
#define MaxG 10005

using namespace std;

FILE *file_in = fopen("rucsac.in", "r");
FILE *file_out = fopen("rucsac.out", "w");

int d[MaxN][MaxG], N, G, v, w, Max = 0;

int main() {

    fscanf(file_in, "%d %d", &N, &G);

    for (int i = 0; i < N; i++) {
        fscanf(file_in, "%d %d", &w, &v);
        for (int j = 0; j <= G; j++) {
            d[i + 1][j] = max(d[i + 1][j], d[i][j]);
            Max = max(d[i + 1][j], Max);
            if (j + w <= G) {
                d[i + 1][j + w] = max(d[i + 1][j + w], d[i][j] + v);
                Max = max(d[i + 1][j + w], Max);
            }
        }
    }

    fprintf(file_out, "%d\n", Max);

    return 0;
}