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

int n, gmax;
int w[5001], p[10001];
int dp[2][10001];

int main() {

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

    fin >> n >> gmax;

    for (int i = 1; i<=n; i++) {
        fin >> w[i] >> p[i];
    }

    for (int i = 1; i<=n; i++) {
        for (int cw = 0; cw <= gmax; cw++) {
            dp[1][cw] = dp[0][cw];

            if (cw >= w[i]) {
                dp[0][cw] = max(dp[0][cw], dp[1][cw-w[i]]+p[i]);
            }
        }
    }

    fout << dp[0][gmax];

    fin.close();
    fout.close();

    return 0;
}