#include<iostream>
#include<fstream>
using namespace std;

ifstream fin("rucsac.in");
ofstream fout("rucsac.out");

int g[5001], p[5001], freq[10001], i, j, N, G, maxi;

int main() {
    fin >> N >> G;
    maxi = 0;
    for(i = 0; i < N; i++) {
        fin >> g[i] >> p[i];
        for(j = G; j > 0; j--) {
            if(freq[j] != 0) {
                if(j + g[i] <= G) {
                    if(freq[j + g[i]] < p[i] + freq[j]) {
                        freq[j + g[i]] = p[i] + freq[j];
                        if(freq[j + g[i]] > maxi) {
                            maxi = freq[j + g[i]];
                        }
                    }
                }
            }
            if(j == g[i]) {
                if(freq[j] < p[i]) {
                    freq[j] = p[i];
                    if(freq[j] > maxi) {
                        maxi = freq[j];
                    }
                }
            }
        }
    }
    fout << maxi;
    fin.close();
    fout.close();
    return 0;
}