#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define inFile "rucsac.in"
#define outFile "rucsac.out"
#define MAX_G 10000
#define MAX_N 5000

FILE *in = fopen(inFile, "r");
FILE *out = fopen(outFile, "w");

int W[MAX_N + 1];
int P[MAX_N + 1];
int D_OLD[MAX_G + 1];
int D_NEW[MAX_G + 1];

int main() {
    int N, G, i, w, k;
    
    fscanf(in, "%d %d", &N, &G);
    for(i = 1; i <= N; i++)
        fscanf(in, "%d %d", &W[i], &P[i]);
    
    for(i = 1; i <= N; i++) {
        for(w = 1; w <= G; w++) {
            if(W[i] > w) {
                D_NEW[w] = D_OLD[w];
            }
            else {
                D_NEW[w] = max(D_OLD[w], D_OLD[w - W[i]] + P[i]);
            }
        }
        memcpy(D_OLD, D_NEW, sizeof(D_NEW));
    }
    
    fprintf(out, "%d\n", D_NEW[G]);
    
    fclose(in);
    fclose(out);
    
    return 0;
}