#include <fstream>

using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int gr[5001],profit[5001],dp[5001][10001];
int n,g;
int main()
{   fi>>n>>g;
    for(int i=1;i<=n;i++) fi>>gr[i]>>profit[i];
    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) if(profit[i]>profit[j]) {swap(gr[i],gr[j]);swap(profit[i],profit[j]);}
    //for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) if(gr[i]<gr[j]) {swap(gr[i],gr[j]);swap(profit[i],profit[j]);}
   // for(int i=1;i<=n;i++) fo<<gr[i]<<" "<<profit[i]<<'\n';
    for(int i=1;i<=n;i++) for(int j=1;j<=g;j++){
            if(j>=gr[i]) dp[i][j]=max(dp[i-1][j],profit[i]+dp[i-1][j-gr[i]]);
           else dp[i][j]=dp[i][j-i];
    }
    //for(int i=1;i<=n;i++){ for(int j=1;j<=g;j++) fo<<dp[i][j]<<" "; fo<<'\n';}
    fo<<dp[n][g];
    return 0;
}