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

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

const int nmax = 5005;
int p[nmax], w[nmax], dp[nmax];

int main() {
    ios_base :: sync_with_stdio(false);
    int n, g, i, j, sol = 0;
    fin >> n >> g;
    for(i = 1; i <= n; i++) {
        fin >> 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(dp[j + w[i]] > sol) {
                    sol = dp[j + w[i]];
                }
            }
        }
    }
    fout << sol;
    fin.close();
    fout.close();
    return 0;
}