#include <fstream>
#define int unsigned long long
using namespace std;
ifstream cin("rucsac.in");
ofstream cout("rucsac.out");
int G[5005],V[5005];
int d[5005];
int32_t main()
{
    int n,g;
    cin>>n>>g;
    for(int i=1;i<=n;i++){
        cin>>G[i]>>V[i];
    }
    for(int i=1;i<=n;i++){
        for(int j=g;j>=G[i];j--){
            d[j]=max(d[j],d[j-G[i]]+V[i]);
        }
    }
    int ans=0;
    for(int i=1;i<=g;i++){
        ans=max(ans,d[i]);
    }
    cout<<ans;
    return 0;
}