#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[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 = g; c >= w[i]; --c)
            dp[c] = max(dp[c], p[i] + dp[c - w[i]]);

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