#include <iostream>
#include <fstream>
#define maxN 5002
#define maxG 10002
#define inf 9999999

using namespace std;

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

int n, G, D[maxN][maxG], W[maxN], P[maxN];

int main () {
    fin >> n >> G;
    for (int i = 1; i <= n; i++) {
        fin >> W[i] >> P[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= G; ++j) {
            D[i][j] = D[i-1][j];
            if (W[i] <= j) {
                D[i][j] = max(D[i-1][j], D[i-1][j-W[i]] + P[i]);
            }
        }
    }
    fout << D[n][G];
}