#include <bits/stdc++.h>
using namespace std;
#define NMAX 5001
#define GMAX 10001

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

int n, g;
int w[NMAX], p[NMAX];
int dp[NMAX][GMAX];

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 c = 0; c <= g; ++c) {
            dp[i][c] = dp[i-1][c];
            if (w[i] <= c)
                dp[i][c] = max(dp[i][c], p[i] + dp[i-1][c - w[i]]);
        }

    fout << dp[n][g] << "\n";
    return 0;
}