#include <bits/stdc++.h>

using namespace std;
int n,k,rez=0;
struct sigma
{
    int cost,greutate;
};
sigma v[5005];
vector<vector<int>>maxp;
 int Rezolv(int a,int c)
{
    if(a==n+1)
        return 0;
    if(maxp[a][c]==-1)
    {
        maxp[a][c]=Rezolv(a+1,c);
        if(c+v[a].greutate<=k)
            maxp[a][c]=max(maxp[a][c],Rezolv(a+1,c+v[a].greutate)+v[a].cost);
    }
    return maxp[a][c];

}
int main()
{
    ifstream cin("rucsac.in");
    ofstream cout("rucsac.out");
  cin>>n>>k;
  maxp.resize(n+1);
  for(int i=0;i<=n;i++)
  {
      maxp[i].resize(k+1);
    for(int j=0;j<=k;j++)
    maxp[i][j]=-1;
  }
  for(int i=1;i<=n;i++)
    cin>>v[i].greutate>>v[i].cost;
    for(int i=n;i>0;i--)
    {
        maxp[i].resize(k+1);
       for(int j=0;j<=k;j++)
       {

    Rezolv(i,j);
       }
       if(i<n)
        maxp[i+1].clear();
    }
  cout<<Rezolv(1,0);

    return 0;
}