#include<fstream>
using namespace std;
ifstream fin("rucsac.in");
ofstream fout("rucsac.out");
int n, gm, i, j;
int g[5000], pret[5000], d[5000][5000];
int main() {
    fin >> n >> gm;
    for (i = 1; i <= n; i++) {
        fin >> g[i];
        fin >> pret[i];
    }
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= gm; j++) {
            if (j < g[i])
                d[i][j] = d[i - 1][j];
            else
                d[i][j] = max(d[i - 1][j], d[i - 1][j - g[i]] + pret[i]);
        }
    }
    fout << d[n][gm];
}