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

#define MaxG 10005

using namespace std;

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

int d[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 = G - w; j >= 0; j--) {
            d[j + w] = max(d[j + w], d[j] + v);
            Max = max(d[j + w], Max);
        }
    }

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

    return 0;
}