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

int n, gmax;
int w[10001];
int p[5001];
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];

   /* for (int i = 1; i<=n; i++) {
        for (int j = 1; j<=gmax; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+p[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
            //cout << dp[i][j] << " ";
        }
        //cout << endl;
    }

    fout << dp[n][gmax];*/



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

    return 0;
}