#include <bits/stdc++.h>
using namespace std;
#define x11 "rucsac.in"
#define x12 "rucsac.out"
ifstream in(x11);
ofstream out(x12);
#define NMAX 10001
#define GMAX 5001
int w[GMAX], p[GMAX], dp[NMAX];
int main() {
    int n, g, i, maxi = 0, j;

    in >> n >> g;

    for(i = 1; i <= n; i++)
        in >> w[i] >> p[i];

    for(i = 1; i <= n; i++) {
        for(j = g - w[i]; j >= 0; j--) {

            if(dp[j + w[i]] < dp[j] + p[i])
                dp[j + w[i]] = dp[j] + p[i];

            if(maxi < dp[j + w[i]])
                maxi = dp[j + w[i]];
        }
    }
    out << maxi;
    return 0;
}