#include<fstream>
using namespace std;
ifstream in("rucsac.in");
ofstream out("rucsac.out");
int dp[2][10001];
int N,G;
int g[5001],val[5001];
int main(){
    in>>N>>G;
    int p=1;
    for(int i=1;i<=N;i++) in>>g[i]>>val[i];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=G;j++) dp[p][j]=0;
        for(int j=1;j<=G;j++) dp[p][j]=dp[!p][j];
        dp[p][ g[i] ] = max( dp[p][ g[i] ] , val[i]);
        for(int j=1;j<=G;j++){
            if( dp[!p][j] != 0 && j+g[i] <= G){
                dp[p][ j + g[i] ] = max( dp[p][ j + g[i] ] , dp[!p][j] + val[i] );
            }
        }
        p=!p;
    }
    int ans=0;
    for(int j=1;j<=G;j++) ans=max(ans,dp[!p][j]);
    out<<ans<<'\n';
    return 0;
}