#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++){
        if(val[i]!=0){

            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;
}