#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 5005
#define NGMAX 10005
using namespace std;

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

int N, G;
int dp[3][NGMAX]; // pt o solutie mult mai eficienta se pot folosi doar 2 linii
vector < pair <int , int> > arr(NMAX);

void cpy(int ind){
    for(int i = 1; i <= G; i++){
        dp[ind - 1][i] = dp[ind][i];
    }
}

int main()
{
    int val, wt;
    fin >> N >> G;
    for(int i = 1; i <= N; i++){
        fin >> wt >> val;
        arr[i].first = wt;
        arr[i].second = val;
    }
    for(int j = 0; j <= G; j++){
            dp[1][j] = dp[1 - 1][j];
            if(arr[1].first <= j){
                dp[1][j] = max(dp[1 - 1][j],dp[1 - 1][j - arr[1].first] + arr[1].second);
            }
    }
    int cnt = 2;
    while(cnt <= N){
        for(int j = 0; j <= G; j++){
            dp[2][j] = dp[1][j];
            if(arr[cnt].first <= j){
                dp[2][j] = max(dp[1][j],dp[1][j - arr[cnt].first] + arr[cnt].second);
            }
        }
        cpy(2);
        cnt++;
    }
    fout << dp[2][G] << "\n";
    return 0;
}