#include <fstream>
#include <vector>
using namespace std;

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

int main() {
    int n, g;
    fin >> n >> g;
    vector<int> w(n+1), p(n+1);
    for (int i = 1; i <= n; i++)
        fin >> w[i] >> p[i];

    vector<int> dp(g+1, 0);
    for (int i = 1; i <= n; i++)
        for (int cw = g; cw >= w[i]; cw--)
            if (dp[cw - w[i]] + p[i] > dp[cw])
                dp[cw] = dp[cw - w[i]] + p[i];

    fout << dp[g];
    return 0;
}