#include <fstream>

using namespace std;
ifstream fi("rucsac.in");
ofstream fo("rucsac.out");
int n,g;
int a[5001],b[10001];
int dp[5001][10001];
int i,j,w,p,k,cnt,o;
int main()
{
  fi>>n>>g;
    for(int t=1;t<=n;t++)
  {
      fi>>w>>p;
            for(j=1;j<=g;j++)
        {
            if(j>=w)
            dp[1][j]=max(dp[0][j],p+dp[0][j-w]);
        }
        for(j=1;j<=g;j++)
        dp[0][j]=dp[1][j];
  }

       fo<<dp[0][g];
//       fo<<endl;
//          for(i=0;i<=n+1;i++)
//    {for(j=0;j<=g+1;j++)
//    fo<<dp[i][j]<<" ";
//    fo<<endl;
//    }

    return 0;
}