// #include <iostream>
#include <fstream>

using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int n,gmax;
int g[5002],p[5002],mat[5002][10002];

int main()
{
    cin>>n>>gmax;
    
    for(int i=1;i<=n;++i)
        cin>>g[i]>>p[i];
        
    for(int i=1;i<=n;++i)
        for(int j=0;j<=gmax;++j){
            int l=i%2;
            mat[l][j]=mat[1-l][j];
            
            if(j>=g[i])
                mat[l][j]=max(mat[l][j],p[i]+mat[1-l][j-g[i]]);
        }
    
    cout<<mat[n%2][gmax];
                
    return 0;
}