#include <iostream>
#include <fstream>
#define NMAX 5000
#define GMAX 10000

using namespace std;

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

int W[NMAX + 1], P[NMAX + 1];
int dp[NMAX + 1][GMAX + 1];

int main()
{
    int N, G;
    fin>>N>>G;

    for(int i = 1; i <= N; i++){
        fin>> W[i] >> P[i];
    }

    for(int i = 1; i <= N; i++){
        for(int k = 1; k <= G; k++){
            if(k >= W[i]){
                dp[i][k] = max(dp[i - 1][k], dp[i - 1][k - W[i]] + P[i]);
            }
            else {
                dp[i][k] = dp[i - 1][k];
            }
        }
    }

    int rez = 0;
    for(int k = 1; k <= G; k++){
        rez = max(rez, dp[N][k]);
    }

    fout<<rez;
}