#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int N, G, W[5005], P[5005];
int d[2][10005];
void citire() {
    fin >> N >> G;
    for (int i=1; i<=N; ++i) {
        fin >> W[i] >> P[i];
    }
}
int main()
{
    citire();
    for (int i=1; i<=N; ++i) {
        for (int j=W[i]; j<=G; ++j) {
            d[2][j]=max(P[i]+d[1][j-W[i]], d[1][j]);
        }
        for (int j=0; j<=G; ++j) {
            d[1][j]=d[2][j];
        }
    }
    fout << d[2][G];
    return 0;
}