#include <fstream>

using namespace std;

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

const int NMAX = 5e3;
const int GMAX = 1e4;

struct obj{

    int greutate, profit;

};

obj v[NMAX + 1];
int dp[GMAX + 1];

int main(){

    int n = 0, g = 0;

    cin >> n >> g;

    for(int i = 1; i <= n; i++)
        cin >> v[i].greutate >> v[i].profit;

    for(int i = 1; i <= n; i++){
        for(int j = g; j >= v[i].greutate; j--){

            if(dp[j] < dp[j - v[i].greutate] + v[i].profit)
                dp[j] = dp[j - v[i].greutate] + v[i].profit;

        }
    }

    cout << dp[g];

    return 0;
}