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

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

const int NMAX = 5001;
const int GMAX = 10001;

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

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

    int maxim = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = G; j >= g[i]; j--) {
            if(dp[j - g[i]] + p[i] > dp[j]) {
                dp[j] = dp[j - g[i]] + p[i];
                maxim = max(maxim, dp[j]);
            }
        }
    }

    fout<<maxim;
    fin.close();
    fout.close();
    return 0;
}