#include <iostream>
#include <algorithm>
#include <climits>
#include <vector>
#include <fstream>

using namespace std;

typedef pair <int, int> pereche;

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

vector<pereche> data;
int Gmax, DP[5001][10001], n;

void read() {
    in >> n >> Gmax;
    int x, y;
    while(in >> x >> y){
        data.push_back({x, y});
    }
}

void print() {
    for(int i = 0; i <= data.size(); i++){
        for(int j = 0; j <= Gmax; j++){
            cout << DP[i][j] << " ";
        }
        cout << '\n';
    }
}

void solve(){

    for(int i = 1; i <= data.size(); i++){
        for(int j = 0; j <= Gmax; j++){
            if(j >= data[i-1].first)
                DP[i][j] = max(data[i-1].second + DP[i-1][j - data[i-1].first], DP[i-1][j]);
            DP[i][j] = max(DP[i][j], DP[i-1][j]);
        }

    }
   // print();
    out << DP[data.size()][Gmax] << '\n';

}

int main() {
    read();
    solve();
    return 0;
}