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

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

int main() {

    ifstream fin("rucsacDP.in");
    ofstream fout("rucsacDP.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 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;
}